Удаление элемента из массива

Решение

Понимание задачи

Нужно удалить все вхождения заданного элемента из массива, модифицировав его на месте, и вернуть новую длину массива. Элементы после новой длины могут быть произвольными.

Подход

Используем двухпроходный алгоритм с двумя индексами:

1. k — позиция для следующего элемента, который не равен val
2. i — текущая позиция в массиве

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

Реализация и тесты

def removeElement(nums: list[int], val: int) -> int:
    """Удаляет все вхождения val из массива на месте. Возвращает новую длину."""
    k = 0  # Индекс для следующего элемента != val
    
    for i in range(len(nums)):
        if nums[i] != val:
            nums[k] = nums[i]
            k += 1
    
    return k

Тестирование

import pytest

class TestRemoveElement:
    def test_basic_example(self):
        nums = [3, 2, 2, 3]
        new_len = removeElement(nums, 3)
        assert new_len == 2
        assert nums[:new_len] == [2, 2]
    
    def test_no_matching_elements(self):
        nums = [1, 2, 3, 4, 5]
        new_len = removeElement(nums, 6)
        assert new_len == 5
        assert nums[:new_len] == [1, 2, 3, 4, 5]
    
    def test_all_elements_to_remove(self):
        nums = [5, 5, 5, 5]
        new_len = removeElement(nums, 5)
        assert new_len == 0
        assert nums[:new_len] == []
    
    def test_single_element_matches(self):
        nums = [5]
        new_len = removeElement(nums, 5)
        assert new_len == 0
    
    def test_scattered_elements(self):
        nums = [1, 2, 1, 3, 1, 4]
        new_len = removeElement(nums, 1)
        assert new_len == 3
        assert nums[:new_len] == [2, 3, 4]
    
    def test_empty_array(self):
        nums = []
        new_len = removeElement(nums, 5)
        assert new_len == 0
    
    def test_in_place_modification(self):
        nums = [1, 2, 3]
        original_id = id(nums)
        removeElement(nums, 2)
        assert id(nums) == original_id
    
    def test_negative_values(self):
        nums = [-1, 0, -1, 2, -1, 3]
        new_len = removeElement(nums, -1)
        assert new_len == 3
        assert nums[:new_len] == [0, 2, 3]

Ключевые аспекты QA

• ✅ Граничные случаи: пустой массив, один элемент
• ✅ Полные совпадения: все элементы равны val
• ✅ Отсутствие совпадений: нет элементов для удаления
• ✅ Разные позиции: элементы в начале, середине, конце
• ✅ Отрицательные числа: проверка со знаками
• ✅ Модификация на месте: O(1) дополнительная память