Легкий
Проблема
Учитывая массив nums и значение val, удалите все экземпляры этого значения на месте и верните новую длину.
Не выделяйте дополнительное пространство для другого массива, вы должны сделать это, изменив входной массив на месте с O(1) дополнительной памяти.
Порядок элементов можно изменить. Неважно, что вы оставите за пределами новой длины.
Пример 1:
Given nums = [3,2,2,3], val = 3, Your function should return length = 2, with the first two elements of nums being 2. It doesn't matter what you leave beyond the returned length.
Пример 2:
Given nums = [0,1,2,2,3,0,4,2], val = 2, Your function should return length =5
, with the first five elements ofnums
containing0
,1
,3
,0
, and 4. Note that the order of those five elements can be arbitrary. 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 = removeElement(nums, val); // 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]); }
Решение
Используйте два указателя i
и j
. i
обозначает конец списка, в котором каждый элемент не равен заданному val
. И j
для перебора всего списка. Как только j
обнаружил, что элемент не равен val
, i
должен продвинуться на один шаг вперед и сохранить текущий элемент в j
.
Сложность
Он выполняет заданное nums
один раз, что занимает O(n) раз, если n
означает длину nums
.
И, очевидно, он использует только O(1) дополнительного пространства.