Структуры - Алгоритмы - LeetCode - 27. Remove Element

Дано: целочисленный массив nums и целое число val, требуется удалить все вхождения val в массив. Вернуть количество оставшихся элементов в nums. (Изменить нужно исходный массив, а не создавать новый).

Пример:
Вход: nums = [3,2,2,3], val = 3
Выход: 2

Ограничения:
0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

Решение(Python):

1) C использованием поверхностной копии и генераторного выражения

def removeElement(nums: List[int], val: int) -> int:
nums[:] = [x for x in nums if x != val]
return len(nums)

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

Временная сложность: цикл дает нам сложность O(n)

Пространственная сложность: поскольку мы создаём новый список, то O(n)

2) Не рекомендованный вариант

def removeElement(nums: List[int], val: int) -> int:
while val in nums: nums.remove(val)

Циклом перебираем все заданный значения val и используя метод .remove удаляем их. Return не требуется так как мы редактируем исходный массив.

Временная сложность: цикл дает нам сложность O(n) и nums.remove(val) это O(n), получаем O(n^2)

Пространственная сложность: O(1).

3) Оптимальный вариант

def removeElement(nums: List[int], val: int) -> int:
index = 0
for i in range(len(nums)):
if nums[i] != val:
nums[index] = nums[i]
index += 1
return index

Создаём вспомогательную переменную и прибавляем к ней все элементы не равные заданному значению, параллельно переназначая индексы элементов.

Временная сложность: цикл дает нам сложность O(n)

Пространственная сложность: вспомогательная переменная даёт сложность O(1).