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

Задача.

Дан отсортированный массив целых чисел, в котором возможны дубликаты. Нужно удалить дубликаты 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;
}