Легкий
Проблема
Учитывая отсортированный массив nums, удалите дубликаты на месте, чтобы каждый элемент отображался только один раз, и верните новую длину.
Не выделяйте дополнительное пространство для другого массива, вы должны сделать это, модифицируя входной массив на месте с O(1) дополнительной памяти.
Пример 1:
Given nums = [1,1,2], Your function should return length =2
, with the first two elements ofnums
being1
and2
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 ofnums
being modified to0
,1
,2
,3
, and4
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) дополнительного места.