Легкий

Проблема

Учитывая отсортированный массив nums, удалите дубликаты на месте, чтобы каждый элемент отображался только один раз, и верните новую длину.

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

Пример 1:

Given nums = [1,1,2],
Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively.
It doesn't matter what you leave beyond the returned length.

Пример 2:

Given nums = [0,0,1,1,1,2,2,3,3,4],
Your function should return length = 5, with the first five elements of nums being modified to 0, 1, 2, 3, and 4 respectively.
It doesn't matter what values are set beyond the returned length.

Пояснение:

Не знаете, почему возвращаемое значение является целым числом, а ваш ответ — массивом?

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

Внутренне вы можете думать об этом:

// nums is passed in by reference. (i.e., without making a copy)
int len = removeDuplicates(nums);
// any modification to nums in your function would be known by the caller.
// using the length returned by your function, it prints the first len elements.
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

Решение

Используйте параметр, чтобы отслеживать каждый отдельный элемент в списке. Начните со второго элемента списка, чтобы элемент отслеживания был инициализирован первым элементом.

Сложность

Список повторяется только один раз и занимает всего O(n) время. И для этого требуется всего O(1) дополнительного места.