26. Удалить повторы из отсортированного массива (Remove Duplicates from Sorted Array)

Задание.

Получен целочисленный массив nums, отсортированный в порядке неубывания.

Нужно удалить дубликаты на месте (in-place) таким образом, чтобы каждый уникальный элемент появлялся только один раз. Относительный порядок элементов должен быть сохранен неизменным.

Поскольку в некоторых языках невозможно изменить длину массива, вместо этого вы должны поместить результат в первую часть массива nums. Более формально, если после удаления дубликатов осталось k элементов, то первые k элементов nums должны содержать конечный результат. Не имеет значения, что вы оставляете за пределами первых k элементов.

Верните k после размещения конечного результата в первых k слотах nums.

Не выделяйте дополнительное пространство для другого массива. Вы должны сделать это, изменив входной массив на месте с помощью O(1) дополнительной памяти.

Традиционная экспертиза

Эксперт протестирует ваше решение с помощью следующего кода:

int[] nums = [...]; // начальный массив
int[] expectedNums = [...]; // ожидаемый ответ правильного размера

int k = removeDuplicates(nums); // вызов нашей реализации

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

Если все утверждения пройдут, решение будет считаться принятым.

Пример 1.

Входные данные: nums = [1,1,2]

Результат: 2, nums = [1,2,_]

Пояснение: Ваша функция должна вернуть k = 2, причем первые два элемента nums равны 1 и 2 соответственно. Не имеет значения, что вы оставляете за пределами возвращаемого k (следовательно, они являются символами подчеркивания).

Пример 2.

Входные данные: nums = [0,0,1,1,1,2,2,3,3,4]

Результат: 5, nums = [0,1,2,3,4, _, _, _, _, _]

Пояснение: Ваша функция должна вернуть k = 5, причем первые пять элементов nums должны быть 0, 1, 2, 3 и 4 соответственно. Не имеет значения, что вы оставляете за пределами возвращаемого k (следовательно, они являются символами подчеркивания).

Решение.

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int k = 1, n = nums.size();
        if(n == 0) {
            return 0;
        }
        for(int i = 1; i < n; i++) {
            if(nums[i] != nums[i-1]) {
                nums[k++] = nums[i];
            }
        }
        return k;
    }
};