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

Ответ: Удаление дубликатов из отсортированного списка

Это классическая задача на собеседовании. Ответ: O(n) — линейное время, где n — количество элементов в списке.

Почему O(n)?

Поскольку список уже отсортирован, дубликаты будут находиться рядом друг с другом. Мы можем пройти по списку один раз и удалить дубликаты, что требует линейного времени.

Решение 1: Two-pointer approach (оптимальное)

public class RemoveDuplicates {
    
    // Удаление дубликатов на месте (in-place)
    // Time: O(n)
    // Space: O(1)
    public static int removeDuplicates(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        
        // Два указателя
        int writeIndex = 0;  // Индекс для записи уникальных элементов
        
        for (int i = 1; i < arr.length; i++) {
            // Если текущий элемент отличается от предыдущего
            if (arr[i] != arr[writeIndex]) {
                writeIndex++;
                arr[writeIndex] = arr[i];  // Записываем уникальный элемент
            }
            // Если элемент дубликат, пропускаем его
        }
        
        return writeIndex + 1;  // Количество уникальных элементов
    }
    
    public static void main(String[] args) {
        int[] arr = {1, 1, 2, 2, 2, 3, 4, 4, 5};
        int uniqueCount = removeDuplicates(arr);
        
        System.out.println("Количество уникальных элементов: " + uniqueCount);
        System.out.print("Массив: ");
        for (int i = 0; i < uniqueCount; i++) {
            System.out.print(arr[i] + " ");
        }
        // Output: Количество уникальных элементов: 5
        // Output: Массив: 1 2 3 4 5
    }
}

Пошаговое выполнение

Исходный массив: [1, 1, 2, 2, 2, 3, 4, 4, 5]
Индексы:         0  1  2  3  4  5  6  7  8

Шаг 1: writeIndex = 0, i = 1
  arr[1] = 1, arr[0] = 1 → они равны, пропускаем
  Массив: [1, 1, 2, 2, 2, 3, 4, 4, 5]

Шаг 2: writeIndex = 0, i = 2
  arr[2] = 2, arr[0] = 1 → они разные!
  writeIndex++ → writeIndex = 1
  arr[1] = 2
  Массив: [1, 2, 2, 2, 2, 3, 4, 4, 5]

Шаг 3: writeIndex = 1, i = 3
  arr[3] = 2, arr[1] = 2 → они равны, пропускаем

Шаг 4: writeIndex = 1, i = 4
  arr[4] = 2, arr[1] = 2 → они равны, пропускаем

Шаг 5: writeIndex = 1, i = 5
  arr[5] = 3, arr[1] = 2 → они разные!
  writeIndex++ → writeIndex = 2
  arr[2] = 3
  Массив: [1, 2, 3, 2, 2, 3, 4, 4, 5]

Шаг 6: writeIndex = 2, i = 6
  arr[6] = 4, arr[2] = 3 → они разные!
  writeIndex++ → writeIndex = 3
  arr[3] = 4
  Массив: [1, 2, 3, 4, 2, 3, 4, 4, 5]

Шаг 7: writeIndex = 3, i = 7
  arr[7] = 4, arr[3] = 4 → они равны, пропускаем

Шаг 8: writeIndex = 3, i = 8
  arr[8] = 5, arr[3] = 4 → они разные!
  writeIndex++ → writeIndex = 4
  arr[4] = 5
  Массив: [1, 2, 3, 4, 5, 3, 4, 4, 5]

Результат: Первые 5 элементов = [1, 2, 3, 4, 5]
Время: 8 итераций (n-1 для массива длины 9)

Анализ сложности

Время выполнения:
- Цикл: O(n)       (один проход по массиву)
- Сравнение: O(1)  (простое целочисленное сравнение)
- Итого: O(n)

Память:
- O(1)  (используем только два указателя, никакой доп. памяти)

Решение 2: С использованием List

public class RemoveDuplicatesFromList {
    
    // С использованием ArrayList
    // Time: O(n)
    // Space: O(k) где k — количество уникальных элементов
    public static List<Integer> removeDuplicates(List<Integer> list) {
        if (list == null || list.isEmpty()) {
            return list;
        }
        
        List<Integer> result = new ArrayList<>();
        int prev = list.get(0);
        result.add(prev);
        
        for (int i = 1; i < list.size(); i++) {
            int current = list.get(i);
            if (current != prev) {
                result.add(current);
                prev = current;
            }
        }
        
        return result;
    }
    
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 1, 2, 2, 2, 3, 4, 4, 5);
        List<Integer> unique = removeDuplicates(list);
        System.out.println(unique);
        // Output: [1, 2, 3, 4, 5]
    }
}

Решение 3: С использованием Iterator (в-месте в List)

public class RemoveDuplicatesInPlace {
    
    // Удаление дубликатов из List в-месте
    // Time: O(n)
    // Space: O(1)
    public static void removeDuplicates(List<Integer> list) {
        if (list == null || list.size() <= 1) {
            return;
        }
        
        Iterator<Integer> iterator = list.iterator();
        Integer prev = iterator.next();
        
        while (iterator.hasNext()) {
            Integer current = iterator.next();
            if (current.equals(prev)) {
                iterator.remove();  // Удаляем дубликат
            } else {
                prev = current;
            }
        }
    }
    
    public static void main(String[] args) {
        List<Integer> list = new ArrayList<>(Arrays.asList(1, 1, 2, 2, 2, 3, 4, 4, 5));
        removeDuplicates(list);
        System.out.println(list);
        // Output: [1, 2, 3, 4, 5]
    }
}

Сравнение подходов

┌─────────────────────┬──────────┬──────────┬──────────────────────┐
│ Подход              │ Время    │ Память   │ Примечание            │
├─────────────────────┼──────────┼──────────┼──────────────────────┤
│ Two-pointer (array) │ O(n)     │ O(1)     │ Лучший выбор          │
│ ArrayList           │ O(n)     │ O(k)     │ Новый список          │
│ Iterator.remove()   │ O(n²)*   │ O(1)     │ Зависит от реализации │
│ Stream.distinct()   │ O(n)     │ O(n)     │ Функциональный стиль  │
└─────────────────────┴──────────┴──────────┴──────────────────────┘
* ArrayList.remove() это O(n), поэтому общее O(n²) в худшем случае

Решение 4: С использованием Stream API

public class RemoveDuplicatesStream {
    
    // Функциональный подход
    // Time: O(n)
    // Space: O(n)
    public static List<Integer> removeDuplicates(List<Integer> list) {
        return list.stream()
                   .distinct()
                   .collect(Collectors.toList());
    }
    
    public static void main(String[] args) {
        List<Integer> list = Arrays.asList(1, 1, 2, 2, 2, 3, 4, 4, 5);
        List<Integer> unique = removeDuplicates(list);
        System.out.println(unique);
        // Output: [1, 2, 3, 4, 5]
    }
}

Практический тест производительности

public class PerformanceTest {
    
    public static void main(String[] args) {
        // Создаём отсортированный список с дубликатами
        int[] arr = new int[1_000_000];
        for (int i = 0; i < arr.length; i++) {
            arr[i] = i / 10;  // Каждое число повторяется 10 раз
        }
        
        // Тест 1: Two-pointer (самый быстрый)
        long start = System.nanoTime();
        removeDuplicatesTwoPointer(arr);
        long duration = System.nanoTime() - start;
        System.out.println("Two-pointer: " + duration / 1_000_000 + "ms");
        
        // Тест 2: ArrayList
        List<Integer> list = new ArrayList<>();
        for (int num : arr) {
            list.add(num);
        }
        start = System.nanoTime();
        removeDuplicatesList(list);
        duration = System.nanoTime() - start;
        System.out.println("ArrayList: " + duration / 1_000_000 + "ms");
        
        // Тест 3: Stream
        start = System.nanoTime();
        list.stream().distinct().collect(Collectors.toList());
        duration = System.nanoTime() - start;
        System.out.println("Stream: " + duration / 1_000_000 + "ms");
    }
    
    // Вспомогательные методы
    static int removeDuplicatesTwoPointer(int[] arr) {
        int write = 0;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] != arr[write]) {
                arr[++write] = arr[i];
            }
        }
        return write + 1;
    }
    
    static List<Integer> removeDuplicatesList(List<Integer> list) {
        List<Integer> result = new ArrayList<>();
        Integer prev = null;
        for (Integer curr : list) {
            if (!curr.equals(prev)) {
                result.add(curr);
                prev = curr;
            }
        }
        return result;
    }
}

Ответ на собеседовании

Вот как я бы ответил на собеседовании:

Вопрос: "Сколько времени понадобится на удаление дубликатов из отсортированного списка?"

Ответ: "Временная сложность — O(n), линейное время, где n — количество элементов.

Поскольку список отсортирован, дубликаты находятся рядом. Мы можем использовать two-pointer подход: один указатель для чтения, другой для записи. Проходим по списку один раз, и когда встречаем новый элемент, записываем его в позицию writeIndex.

Пространственная сложность — O(1), если работаем с массивом на месте, или O(k), если создаём новый список, где k — количество уникальных элементов.

Время выполнения на массиве из 1 млн элементов: ~5-10ms."

Заключение

Ответ: O(n) — линейное время

Это оптимальная сложность, потому что:

1. Нам необходимо посмотреть каждый элемент минимум один раз
2. List отсортирован, поэтому мы можем обойтись одним проходом
3. Two-pointer метод — самый эффективный (O(1) дополнительная память)
4. Это работает быстро даже для больших наборов данных