Задача.

Дан отсортированный массив целых чисел, в котором возможны дубликаты. Нужно удалить дубликаты in-place и вернуть число уникальных элементов в массиве. Например, есть массив: [1, 1, 1, 2, 2, 3, 4, 5, 5, 7, 7, 9]. В результате должно получиться [1, 2, 3, 4, 5, 7, 9, .., .., ....] и число уникальных элементов 7. На троеточие я заменил хвост массива, и нам не важно что там будет после преобразования. Мы будем проверять только первые 7, что они отображают все уникальные числа из массива.

Ссылка на leetcode: https://leetcode.com/problems/remove-duplicates-from-sorted-array/description/

Решение

На ум сразу приходят несколько вариантов решения не in-place. Например, использовать второй массив, в который будем копировать элементы только когда nums[i] != nums[i + 1]. Или использовать HashSet , в который будем помещать элементы массива по мере итераций по нему и проверять видели ли мы этот элемент или нет. Но все эти варианты решения требуют O(n) памяти.

Можно решить используя Two Pointers(два указателя). Один указатель для итераций по массиву, а второй индекс то, куда мы будем копировать уникальный элемент в том же массиве. Копирование будем делать только тогда, когда текущий элемент отличается от следующего. Плюс edge-case для последнего элемента, который мы всегда копируем.

public int removeDuplicates(int[] nums) {
    int k = 0;
    for (int i = 0; i < nums.length; i++) {
        if (i == nums.length - 1 || nums[i] != nums[i + 1]) {
            nums[k++] = nums[i];
        }
    }
    return k;
}

Time Complexity O(n), Space Complexity O(1)

Давайте посмотрим как оно будет работать по шагам для нашего примера.

Вначале i = 0, k = 0:

Далее для i = 1 nums[i] = 1, nums[i + 1] = nums[2] = 1, поэтому ничего не делаем и переходим на следующую итерацию:

Для i = 2, nums[i] = 1, nums[i + 1] = 2. Поэтому копируем 1 в начало массива и увеличиваем k на 1:

Для i = 3 ничего не делаем, т.к. nums[i] = 2, nums[i + 1] = 2. Для i = 4 два соседних элемента не равны. Поэтому копируем и увеличиваем k:

Аналогично повторяем для i = 5 - 10:

Для i = 11, i + 1 = 12 за пределами массива. Поэтому сравнения со следующим не делаем, а просто копируем:

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

Задача.

Решение