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

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

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

Основная идея

Так как массив отсортирован, все дубликаты расположены рядом:

[0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
 ↑     ↑        ↑     ↑  ↑  ↑
 дубликаты находятся рядом

Мы используем:

• k — указатель на позицию для записи следующего уникального элемента
• i — указатель для сканирования массива

Алгоритм:

1. Начинаем с k=1, i=1 (первый элемент всегда уникален)
2. Если nums[i] != nums[i-1] — нашли новый элемент
3. Записываем nums[i] в позицию nums[k]
4. Увеличиваем k и i
5. Продолжаем пока не закончится массив

Решение

class Solution {
    public static int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        
        int k = 1;  // Позиция для записи следующего уникального элемента
        
        // Сканируем с индекса 1
        for (int i = 1; i < nums.length; i++) {
            // Если текущий элемент отличается от предыдущего
            if (nums[i] != nums[i - 1]) {
                // Записываем его на позицию k
                nums[k] = nums[i];
                k++;  // Сдвигаем позицию записи
            }
            // Если элемент дубликат, пропускаем
        }
        
        return k;  // k — количество уникальных элементов
    }
    
    public static void main(String[] args) {
        // Пример 1
        int[] nums1 = {1, 1, 2};
        int result1 = removeDuplicates(nums1);
        System.out.println("Результат: " + result1);  // 2
        System.out.println("Массив: " + Arrays.toString(Arrays.copyOf(nums1, result1)));
        // [1, 2]
        
        // Пример 2
        int[] nums2 = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
        int result2 = removeDuplicates(nums2);
        System.out.println("\nРезультат: " + result2);  // 5
        System.out.println("Массив: " + Arrays.toString(Arrays.copyOf(nums2, result2)));
        // [0, 1, 2, 3, 4]
        
        // Пример 3: массив без дубликатов
        int[] nums3 = {1, 2, 3};
        int result3 = removeDuplicates(nums3);
        System.out.println("\nРезультат: " + result3);  // 3
        
        // Пример 4: все одинаковые
        int[] nums4 = {5, 5, 5, 5};
        int result4 = removeDuplicates(nums4);
        System.out.println("\nРезультат: " + result4);  // 1
    }
}

Пошаговое объяснение

Для массива [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]:

Начальное состояние: k=1, i=1
Массив: [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]
         ↑     ↑
         k     i

Шаг 1: i=1, nums[1]=0 == nums[0]=0 → пропускаем, i++

Шаг 2: i=2, nums[2]=1 != nums[1]=0 → записываем nums[2] в nums[1]
Массив: [0, 1, 1, 1, 1, 2, 2, 3, 3, 4]
         ↑  ↑     ↑
         k  k     i
k++, i++

Шаг 3: i=3, nums[3]=1 == nums[2]=1 → пропускаем, i++

Шаг 4: i=4, nums[4]=1 == nums[3]=1 → пропускаем, i++

Шаг 5: i=5, nums[5]=2 != nums[4]=1 → записываем nums[5] в nums[2]
Массив: [0, 1, 2, 1, 1, 2, 2, 3, 3, 4]
         ↑  ↑  ↑     ↑
         k  k  k     i
k++, i++

Шаг 6: i=6, nums[6]=2 == nums[5]=2 → пропускаем, i++

Шаг 7: i=7, nums[7]=3 != nums[6]=2 → записываем nums[7] в nums[3]
Массив: [0, 1, 2, 3, 1, 2, 2, 3, 3, 4]
         ↑  ↑  ↑  ↑  ↑
         k  k  k  k  i
k++, i++

Шаг 8: i=8, nums[8]=3 == nums[7]=3 → пропускаем, i++

Шаг 9: i=9, nums[9]=4 != nums[8]=3 → записываем nums[9] в nums[4]
Массив: [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]
         ↑  ↑  ↑  ↑  ↑     ↑
         k  k  k  k  k     i
k++, i++

Цикл завершён, k=5, i=10
Ответ: 5 уникальных элементов

Уникальные элементы в начале: [0, 1, 2, 3, 4]

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

Временная сложность: O(n)

• Проходим массив один раз
• Каждый элемент посещается только один раз

Пространственная сложность: O(1)

• Используем только переменные k и i
• Модифицируем массив на месте, без дополнительной памяти

Почему это лучше, чем другие подходы

Плохой подход: использовать HashSet

// O(n) время, но O(n) память!
HashSet<Integer> unique = new HashSet<>();
int k = 0;
for (int num : nums) {
    if (!unique.contains(num)) {
        unique.add(num);
        nums[k++] = num;
    }
}
return k;

Это нарушает требование O(1) памяти.

Плохой подход: сортировать и удалять

// O(n log n) время, не оптимально
Arrays.sort(nums);
// ... затем удалять

Массив уже отсортирован, сортировка — пустая трата времени.

Вариант 2: Если нужны дубликаты с ограничением

Что если каждый элемент может появляться не более K раз?

public static int removeDuplicates(int[] nums, int k) {
    if (nums == null || nums.length == 0) {
        return 0;
    }
    
    int j = 0;  // Позиция записи
    
    for (int i = 0; i < nums.length; i++) {
        // Если j < k или текущий элемент отличается от nums[j-k]
        if (j < k || nums[i] != nums[j - k]) {
            nums[j++] = nums[i];
        }
    }
    
    return j;
}

// Пример: каждый элемент не более 2 раз
int[] nums = {0, 0, 1, 1, 1, 2, 2, 3, 3, 4};
int result = removeDuplicates(nums, 2);
System.out.println(result);  // 8
// [0, 0, 1, 1, 2, 2, 3, 3]

Интеллектуальная улучшенная версия

public static int removeDuplicates(int[] nums) {
    if (nums.length <= 1) return nums.length;
    
    int k = 1;  // k — текущее количество уникальных элементов
    int i = 1;  // i — текущая позиция в массиве
    
    while (i < nums.length) {
        if (nums[i] != nums[i - 1]) {
            nums[k++] = nums[i];
        }
        i++;
    }
    
    return k;
}

Key Points

1. Two-pointer техника — мощный инструмент для отсортированных массивов
2. In-place модификация — важно для использования памяти
3. Отсортированность — это ключ к O(1) памяти
4. Сложность O(n) время, O(1) память — оптимально

Этот паттерн часто встречается в интервью и применяется в более сложных задачах (слияние массивов, удаление дубликатов с ограничением и т.д.).