Дано: целочисленный массив 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).
