LeetCode: 27 Remove Element

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The relative order of the elements may be changed.

Since it’s impossible to change the length of the array in some languages, you must instead have the result placed in the first part of the array nums. More formally, if there are k elements after removing the duplicates, then the first k elements of nums should hold the final result. It does not matter what you leave beyond the first k elements.

Return k after placing the final result in the first k slots of nums.

Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.

Example

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).

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,3,0,4,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 1, 3, 0, and 4.
Note that the relative order of those five elements can be arbitrary.

问题

给定一个整数数组 nums 和一个整数 val，就地移除数组中所有值等于 val 的元素。元素的相对顺序可以改变。

由于在某些语言中无法改变数组的长度，因此必须将结果放在数组 nums 的前部分。更正式地说，移除后，如果数组中有 k 个元素，那么 nums 的前 k 个元素应该包含最终结果。之后的元素无关紧要。

返回移除后数组中 k 的值，并将结果放在数组的前 k 个位置。

不能为另一个数组分配额外的空间，必须通过使用 O(1) 的额外内存就地修改输入数组。

例子

输入: nums = [3,2,2,3], val = 3
输出: 2, nums = [2,2,_,_]
解释: 函数应返回 k = 2，前两个元素应为 2。

输入: nums = [0,1,2,2,3,0,4,2], val = 2
输出: 5, nums = [0,1,3,0,4,_,_,_]
解释: 函数应返回 k = 5，前五个元素应为 0，1，3，0 和 4。

Iterative Solution

Approach: Two Pointers / 双指针

We can solve this problem by using the two-pointer technique. One pointer (i) iterates over the array, while the second pointer (k) keeps track of the position where the next valid (non-val) element should be placed.

Approach Explanation / 方法解释

Two Pointers: One pointer iterates through the array (i), and the second pointer (k) tracks the next position for valid elements.
Place Valid Elements: When nums[i] is not equal to val, copy it to nums[k] and increment k.
Return k: After processing all elements, return k as the count of valid elements.

Iterative Algorithm / 迭代算法

Initialize k = 0 to keep track of the position for valid elements.
Iterate through the array with i:
- If nums[i] != val, copy nums[i] to nums[k] and increment k.
Return k, the count of valid elements.

Iterative Implementation / 迭代实现

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        k = 0  # Pointer for the next position of valid elements

        # Iterate through the array
        for i in range(len(nums)):
            if nums[i] != val:
                nums[k] = nums[i]
                k += 1

        # Return the number of valid elements
        return k

Iterative Solution Explanation / 迭代解决方案解释

Initialize Pointer k / 初始化指针 k
```
k = 0
```
- English: Initialize k to track the position where the next valid element should be placed.
- Chinese: 初始化 k，用于跟踪下一个有效元素应放置的位置。
Iterate Through the Array / 遍历数组
```
for i in range(len(nums)):
   if nums[i] != val:
       nums[k] = nums[i]
       k += 1
```
- English: For each element, if it is not equal to val, place it at nums[k] and move k forward.
- Chinese: 对于每个元素，如果它不等于 val，将其放置在 nums[k]，并将 k 前移。
Return the Count of Valid Elements / 返回有效元素的数量
```
return k
```
- English: Return k, which represents the number of valid elements in the array.
- Chinese: 返回 k，表示数组中有效元素的数量。

Recursive Solution

Approach: Recursive Two Pointers / 递归双指针

We can implement the two-pointer approach recursively. The recursion will iterate over each element, checking if it is equal to val, and place valid elements at the correct position.

Recursive Algorithm / 递归算法

Initialize k = 0 to track the next position for valid elements.
Recursively process each element:
- If nums[i] != val, place nums[i] at nums[k] and increment k.
- Process the next element recursively until the array is fully traversed.
Base case: If i == len(nums), return k.

Recursive Implementation / 递归实现

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        def recursive(i, k):
            if i == len(nums):
                return k
            if nums[i] != val:
                nums[k] = nums[i]
                k += 1
            return recursive(i + 1, k)

        return recursive(0, 0)

Recursive Solution Explanation / 递归解决方案解释

Base Case: End of Array / 基本情况：数组末尾
```
if i == len(nums):
   return k
```
- English: If we have processed all elements, return k, which is the count of valid elements.
- Chinese: 如果我们已经处理了所有元素，返回 k，即有效元素的数量。
Recursive Case: Process Each Element / 递归情况：处理每个元素
```
if nums[i] != val:
   nums[k] = nums[i]
   k += 1
return recursive(i + 1, k)
```
- English: For each element, if it is not equal to val, place it at nums[k] and increment k. Recursively process the next element.
- Chinese: 对于每个元素，如果它不等于 val，将其放置在 nums[k]，并递归处理下一个元素。

Complexity Analysis / 复杂度分析

Time Complexity / 时间复杂度: O(n), where n is the number of elements in the array. We process each element once.
Space Complexity / 空间复杂度:
- Iterative Solution: O(1), since no extra space is used.
- Recursive Solution: O(n), due to the recursion stack.

Key Concept / 关键概念

Two Pointers / 双指针: The two-pointer technique allows us to efficiently remove elements in-place by tracking the position of the next valid element.
Recursion / 递归: The recursive solution processes each element individually, updating the array and tracking valid elements without using a loop.

Summary / 总结

English: We can solve the problem of removing elements in an array using the two-pointer technique, either iteratively or recursively. Both approaches efficiently modify the array in place and return the number of valid elements.
Chinese: 我们可以使用双指针技术解决从数组中删除元素的问题，

迭代或递归方法均可。这两种方法都能有效地就地修改数组，并返回有效元素的数量。

Tips / 提示

English: Ensure to handle the case when all elements in the array are equal to val by returning k = 0.
Chinese: 确保处理数组中所有元素都等于 val 的情况，返回 k = 0。

5 More Similar Questions / 推荐5问题

Recommended Resources / 推荐资源

English: Practice problems related to in-place array modification to get comfortable with two-pointer techniques.
Chinese: 练习与就地修改数组相关的问题，以熟练掌握双指针技术。

Remove Element – Leetcode 27 – Python by NeetCode

Post Views: 43

CODEBITWAVE