27. Remove Element

Задача

Задача

Дан целочисленный массив nums и целое число val , удалите все вхождения val в nums на месте. Порядок элементов может быть изменен. Затем верните количество элементов в nums , которые не равны val . Учитывайте количество элементов в nums , которые не равны val , равное k . Чтобы задача была принята, вам нужно сделать следующее:

• Измените массив nums так, чтобы первые k элементов nums содержали элементы, которые не равны val. Остальные элементы nums не важны, как и размер nums.
• Верните k.

Пример 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 (поэтому они подчеркнуты).

Примеры

Пример 1

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

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];
}

Пример 2

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]

Пояснение

Функция возвращает k = 2, первые два элемента — 2. Что после k — неважно.

Пример 3

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]

Пояснение

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

Решение

Решение

// Временная сложность: O(n)
// Пространственная сложность: O(1)
 
var removeElement = function(nums, val) {
    let k = 0; // O(1) - указатель для записи
 
    // O(n) - один проход
    for (let i = 0; i < nums.length; i++) { // O(1) на итерацию
        if (nums[i] !== val) {
            nums[k] = nums[i]; // O(1) - перезапись элемента
            k++;
        }
    }
 
    return k; // O(1)
};