Легкий

Проблема

Учитывая массив 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 of nums containing 0, 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) дополнительного пространства.