移除元素

1. 题目

1.1. 描述

给你一个数组 nums 和一个值 val，你需要原地移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。

假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

更改 nums 数组，使 nums 的前 k 个元素包含不等于 val 的元素。nums 的其余元素和 nums 的大小并不重要。
返回 k。

用户评测：

评测机将使用以下代码测试您的解决方案：

int[] nums = […]; // 输入数组
int val = …; // 要移除的值
int[] expectedNums = […]; // 长度正确的预期答案。
// 它以不等于 val 的值排序。

int k = removeElement(nums, val); // 调用你的实现

assert k == expectedNums.length;
sort(nums, 0, k); // 排序 nums 的前 k 个元素
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}

如果所有的断言都通过，你的解决方案将会通过。

1.2. 示例

示例 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.3. 提示

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

2. 思路

2.1. 迭代法

定义变量k，记录数组中与给定值不同的元素个数，并覆盖数组nums[k++]=nums[i];
时间复杂度为O(n)，空间复杂度为O(1)

2.2. 双指针法

变量l，r分别指向数组的头尾位置
- l遍历数组中元素值不等于给定值
- r遍历数组中元素值等于给定值
- 及时交换两处的元素
最终l>=r时停止循环，此时i处数组值等于给定值的话返回l，不等于给定值时返回l+1
时间复杂度为O(n)，空间复杂度为O(1)

3. 代码

3.1. C++

3.1.1. 迭代法

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

3.1.2. 双指针法

因为0 <= nums.length <= 100，所以需要判断nums.size()==0

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        if(nums.size()==0){
            return 0;
        }
        int l = 0;
        int r = nums.size()-1; 
        while(l<r){
            while(l<r&&nums[l]!=val){
                l++;
            }
            while(l<r&&nums[r]==val){
                r--;
            }
            int temp = nums[l];
            nums[l]=nums[r];
            nums[r]=temp;
        }
        if(nums[l]==val){
            return l;
        }else{
            return l+1;
        }
    }
};

3.2. Java

3.2.1. 迭代法

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

3.2.2. 双指针法

class Solution {
    public int removeElement(int[] nums, int val) {
        if(nums.length==0){
            return 0;
        }
        int l=0;
        int r = nums.length-1;
        while (l<r) {
            while(l<r&&nums[l]!=val){
                l++;
            }
            while(l<r&&nums[r]==val){
                r--;
            }
            int temp = nums[l];
            nums[l]=nums[r];
            nums[r]=temp;
        }
        if(nums[l]==val){
            return l;
        }else{
            return l+1;
        }
    }
}

W.T.的博客

0027.Remove-Element