Remove Element - LeetCode

https://leetcode.com/problems/remove-element/?envType=study-plan-v2&envId=top-interview-150

LeetCode_Sharing.png

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.

Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:

  • Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
  • Return k.
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];
}

Custom Judge:

The judge will test your solution with the following code:

If all assertions pass, then your solution will be accepted.

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

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

Constraints:

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

解析

题目搞清楚非常重要，题目的意思是，给定了一个数组nums，整数val，去除掉nums中所有等于val的值。返回不等于val的元素的个数。

评价方式：

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

也就是将返回的K值和expectedNums的长度进行比较，相等则取nums排序后的前K个，看是不是和期望值一致

指针移动一直是一个比较好的方法。思路也很明确。

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        p1 = 0
        p2 = 0
        k = 0

        while p1 <= len(nums) - 1 and p2 <= len(nums) - 1:
            if nums[p1] != val:
                nums[p2] = nums[p1]
                p2 += 1
                p1 += 1
                k += 1
            else:
                p1 += 1

        return k

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

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

问题概述: 给定一个整数数组 nums 和一个整数 val，要求你原地移除所有数值等于 val 的元素，并返回新的数组长度。这意味着之后的数组中，前这么多的元素都不是 val。

重要的是，被要求在原数组上修改，并且只使用O(1)的额外空间。因此，我们不能使用额外的数组。

解决策略:

  1. 双指针法:
    • 使用两个指针 —— 一个用于遍历数组(i)，另一个指向下一个非val元素应该放置的位置(j)。
    • 对于每个元素，如果它不等于 val，则将其放在 j 的位置，并增加 j。
    • 这是一个原地操作，即原始数组被修改。
  2. 使用C++的STL:
    • C++ 提供了一个标准函数 remove，它可以将需要移除的元素移动到容器的末尾，然后返回指向容器新末尾的迭代器。
    • 通过使用 remove 和 erase，我们可以达到同样的效果。

注意点:

  1. 虽然该问题只要求返回新的数组长度，但根据问题的要求，数组的前 k 个元素应当是所有非 val 的元素，数组后面的元素则不被考虑。
  2. 解决此问题时不需要考虑数组中超过新长度之后的元素。

这个问题主要考察了数组操作的基本技巧和原地修改数组的能力，同时也涉及到了双指针策略的使用。