leetcode数组-移除元素

题目

题目链接：https://leetcode.cn/problems/remove-element/

给你一个数组 nums 和一个值 val，你需要 原地 移除所有数值等于 val 的元素。元素的顺序可能发生改变。然后返回 nums 中与 val 不同的元素的数量。
假设 nums 中不等于 val 的元素数量为 k，要通过此题，您需要执行以下操作：

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

输入：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 个元素之外留下了什么并不重要（因此它们并不计入评测）。

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
	
    }
};

思路 && 代码

1. 采用暴力移除方法

#include <vector>
#include <iostream>
using namespace std;

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        for(int i = 0; i < size; i++) {
            if(nums[i] == val) {
                for(int j = i + 1; j < size; j++){ // 此处是 j = i + 1, 且条件是 j < size，
                    nums[j - 1] = nums[j]; // 所以此处必须是 nums[j-1] = nums[j],而不是nums[j] = nums[j+1]
                }
                i--;
                size--;
            }
        }
        return size;
    }
};
// @lc code=end
int main() {
    Solution obj;
    vector<int> vec = {0,1,2,2,3,0,4,2};
    int val = 2;
    int res = obj.removeElement(vec, val);
    cout << res << endl;
}

时间复杂度：O(n^2)
空间复杂度：O(1)

2. 双指针

第一版代码：

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int size = nums.size();
        int slowIndex = 0;
        int fastIndex = 0;
        while(fastIndex < size){
            if(nums[fastIndex] == val){
                fastIndex++;
            }else{
                nums[slowIndex] = nums[fastIndex];
                slowIndex++;
            }
            fastIndex++;
        }
        return slowIndex;
    }
};

第二版代码： 将以上代码相同类归化后

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

时间复杂度：O(n)
空间复杂度：O(1)

总结

简洁明了的代码不是一次性就能写出来的，先把自己想的思路写出来，调试通后，再看看是否能合并相同的条件和结果，再简化代码。