27. Удалить элемент (Remove Element)

Задание.

Получен целочисленный массив nums и целое значение val

Нужно удалить все вхождения val в nums на месте (in-place). Относительный порядок элементов может быть изменен.

Поскольку в некоторых языках невозможно изменить длину массива, вместо этого вы должны поместить результат в первую часть массива nums.

Более формально: если после удаления дубликатов осталось k элементов, то первые k элементов nums должны содержать конечный результат. Не имеет значения, что вы оставляете за пределами первых k элементов.

Верните k после размещения конечного результата в первых k слотах nums

Не выделяйте дополнительное пространство для другого массива. Нужно сделать задание, изменив входной массив на месте с помощью O(1) дополнительной памяти..

Традиционная экспертиза

Эксперт протестирует ваше решение с помощью следующего кода:

int[] nums = [...]; // Input array
int val = ...; // Значение, которое нужно удалить
int[] expectedNums = [...]; // Ожидаемый ответ правильного размера.
                            // Отсортированный и не содержащий элементов со значением `val`.

int k = removeElement(nums, val); // Вызов предложенной реализации

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

Если все утверждения пройдут, решение будет считаться принятым.

Пример 1.

Входные данные: nums = [3,2,2,3], val = 3

Результат: 2, nums = [2,2,,]

Пояснение: Функция должна возвратить k = 2, причем первые два элемента nums равны 2. Не имеет значения, что вы оставляете за пределами возвращаемого k (следовательно, они являются символами подчеркивания).

Пример 2.

Входные данные: nums = [0,1,2,2,3,0,4,2], val = 2

Результат: 5, nums = [0,1,4,0,3,,,_]

Пояснение: Функция должна возвратить k = 5, причем первые пять элементов nums содержат 0, 0, 1, 3 и 4. Обратите внимание, что пять элементов могут быть возвращены в любом порядке. Не имеет значения, что вы оставляете за пределами возвращаемого k (следовательно, они являются символами подчеркивания).

Решение.

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int len = nums.size(), k = 0;    
        for(int i = 0; i < len; i++) {
            if(nums[i] != val) {
                nums[k++] = nums[i];
            }
        }
        return k;
    }
};