Задача Remove Element

Уровень: easy

Итак, задачка следующая: дан массив чисел nums и некоторое число val типа int. Нужно удалить все значения массива, которые равны числу val. А в качестве ответа возвращаем количество элементов, которые не равны val.

Пример:
Исходный массив nums: [1,4,1,8,9], число val: 1
Ответ: 3, массив на выходе [4,8,9,_,_]

Ограничения:
1. Длина массива от 1 до 200
2. Значения элементов массива от 0 до 50
3. Значения val от 0 до 20

Ссылочка на задачу, как всегда

Подход к решению:
Задаем текущий индекс равным 0 (он и есть число элементов, которые не равны значению val) .
Нам нужно последовательно обойти все числа массива, если текущий элемент массива не равен значению val, то на место nums[index] мы запишем текущее значение, а индекс увеличим на единицу. Для примера выше был

Итак, код:

public int removeElement(int[] nums, int val) {
    int index = 0;
    for (int i = 0; i < nums.length; i++) {
        if (nums[i] != val) {
            nums[index] = nums[i];
            index++;
        }
    }
    return index;
}

1. Инициализация переменной index, которая указывает, куда именно нужно записывать элементы, которые не равны val.
2. Проход по массиву: цикл for, который проходит по каждому элементу массива nums с использованием индекса i. На каждом шаге проверяется, равен ли текущий элемент nums[i] значению val.
3. Проверка каждого элемента: если nums[i] не равен val, это означает, что данный элемент нужно оставить в массиве.
— Присваивание значения: Алгоритм присваивает nums[index] = nums[i], копируя текущее значение nums[i] в позицию index. Этот шаг заменяет значение в позиции index текущим значением, которое не равно val.
—Сдвиг index: Затем увеличиваем index на 1, чтобы указать, где должен располагаться следующий элемент, который не равен val.
Если nums[i] равен val, то алгоритм просто пропускает его, не изменяя index и переходя к следующему элементу.
4. Возврат результата: после завершения цикла значение index указывает на количество элементов, не равных val. Это также количество элементов, которые мы оставили в начале массива.

Временная сложность: O(n), т.к. придется пройтись по всем элементам массива
Пространственная сложность: O(1), т.к. будет выделено ограниченное кол-во памяти под переменные index и i, которые не зависят от размера входного массива.