Какова временная сложность удаления дубликатов из отсортированного списка в Java

Временная сложность: O(n), где n — количество элементов в списке. Алгоритм проходит по списку ровно один раз. Пространственная сложность: O(1) дополнительной памяти при in-place модификации.

Алгоритм «двух указателей» (in-place): Это оптимальное решение для отсортированного ArrayList.

public int removeDuplicatesFromSortedList(List<Integer> sortedList) {
    if (sortedList == null || sortedList.isEmpty()) {
        return 0;
    }
    int writeIndex = 1; // Указатель для записи уникальных элементов
    for (int readIndex = 1; readIndex < sortedList.size(); readIndex++) {
        // Сравниваем текущий элемент с последним записанным уникальным
        if (!sortedList.get(readIndex).equals(sortedList.get(writeIndex - 1))) {
            sortedList.set(writeIndex, sortedList.get(readIndex));
            writeIndex++;
        }
    }
    // Возвращаем новый размер. Элементы после writeIndex считаются «удаленными».
    return writeIndex;
}

Ключевые моменты:

• Условие: Список должен быть отсортирован, иначе алгоритм не сработает.
• Поведение: Алгоритм сохраняет относительный порядок элементов.
• Для LinkedList: Сложность по времени остается O(n), но операции get и set имеют сложность O(n) каждая, что делает реализацию неэффективной. Для LinkedList лучше использовать итератор.
• Альтернатива (не in-place): Использование LinkedHashSet сохранит порядок, но потребует O(n) дополнительной памяти.