LeetCode — Удалить элемент

Постановка задачи

Учитывая целочисленный массив nums и целочисленное val, удалите все вхождения val в nums in- место. Относительный порядок элементов может быть изменен.

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

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

Не не выделяйте дополнительное пространство для другого массива. Вы должны сделать это, изменив входной массив на месте с помощью O(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];
}

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

Постановка задачи взята с: https://leetcode.com/problems/remove-element

Пример 1:

Input: nums = [3, 2, 2, 3], val = 3
Output: 2, nums = [2, 2, _, _]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Пример 2:

Input: nums = [0, 1, 2, 2, 3, 0, 4, 2], val = 2
Output: 5, nums = [0, 1, 4, 0, 3, _, _, _]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Ограничения:

- 0 <= nums.length <= 100
- 0 <= nums[i] <= 50
- 0 <= val <= 100

Объяснение

Подход грубой силы

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

Затем скопируйте этот новый массив в исходный массив. Но поскольку в постановке задачи уже упоминается, что мы должны сделать это на месте, мы не можем создать новый массив.

Временная сложность описанного выше подхода составляет O(N), но пространственная сложность также составляет O(N).

Использование двух указателей

Мы можем уменьшить сложность пространства и изменить массив на месте, используя два указателя.

Проверим алгоритм.

- if nums.size() == 0
  - return 0

- set i, j = 0

- loop for i = 0; i < nums.size() - 1; i++
  - if nums[i] != val
    - nums[j++] = nums[i] // assign nums[i] to nums[j] and then increment j.

- if nums[i] != val
  - nums[j++] = nums[i] // assign nums[i] to nums[j] and then increment j.

- return j

С++ решение

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        if(nums.size() == 0){
            return 0;
        }

        int i, j = 0;

        for(i = 0; i < nums.size() - 1; i++){
            if(nums[i] != val){
                nums[j++] = nums[i];
            }
        }

        if(nums[i] != val){
            nums[j++] = nums[i];
        }

        return j;
    }
};

Голанг решение

func removeElement(nums []int, val int) int {
    if len(nums) == 0 {
        return 0
    }

    i, j := 0, 0

    for ; i < len(nums) - 1; i++ {
        if nums[i] != val {
            nums[j] = nums[i]
            j++
        }
    }

    if nums[i] != val {
        nums[j] = nums[i]
        j++
    }

    return j
}

Javascript-решение

var removeElement = function(nums, val) {
    if( nums.length == 0 ){
        return 0;
    }

    let i = 0, j = 0;

    for(; i < nums.length - 1; i++){
        if( nums[i] != val ){
            nums[j++] = nums[i];
        }
    }

    if( nums[i] != val ){
        nums[j++] = nums[i];
    }

    return j;
};

Давайте запустим наш алгоритм в пробном режиме, чтобы увидеть, как работает решение.

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

Step 1: if nums.size() == 0
        4 == 0
        false

Step 2: set i, j = 0, 0

Step 3: loop for i = 0; i < nums.size() - 1
        i < 3
        0 < 3
        true

        nums[i] != val
        nums[0] != 3
        3 != 3
        false

        i++
        i = 1

Step 4: loop for i < nums.size() - 1
        i < 3
        1 < 3
        true

        nums[i] != val
        nums[1] != 3
        2 != 3
        true

        nums[j++] = nums[i]
        nums[j] = nums[1]
        nums[0] = 2
        j++
        j = 1

        i++
        i = 2

        nums = [2, 2, 2, 3]

Step 4: loop for i < nums.size() - 1
        i < 3
        2 < 3
        true

        nums[i] != val
        nums[1] != 3
        2 != 3
        true

        nums[j++] = nums[i]
        nums[j] = nums[1]
        nums[1] = 2
        j++
        j = 2

        i++
        i = 3

        nums = [2, 2, 2, 3]

Step 4: loop for i < nums.size() - 1
        i < 3
        3 < 3
        false


Step 5: if nums[i] != val
        nums[3] != 3
        3 != 3
        false

Step 6: return j

So we return the answer as 2.

Первоначально опубликовано на https://alkeshghorpade.me.