代码随想录刷题｜数组 | 移除元素

题目

移除元素

暴力解法

这道题非常有意思，有意思在于这是需要原地操作，也就是在输入的数据中进行修改，暴力解法非常的暴力，也就是每发现一个目标值就把后面的所有值往前移一位。
当然也是有关键点细节的，比如size–的设置，说多无益，看动图和代码最直观。

// 时间复杂度：O(n^2)
// 空间复杂度：O(1)
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++) {
                    nums[j - 1] = nums[j];
                }
                i--; // 因为下标i以后的数值都向前移动了一位，所以i也向前移动一位
                size--; // 此时数组的大小-1
            }
        }
        return size;

    }
};

双指针法

思路就是既然要覆盖出现的目标值，那不如把其他非目标值一直往前填充，最后慢指针指向的就是最终的数组大小。
这是我写的代码，比较简单

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

这是卡哥的代码，比较高级（其实思路都一样）

// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slowIndex = 0;
        for (int fastIndex = 0; fastIndex < nums.size(); fastIndex++) {
            if (val != nums[fastIndex]) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }
        return slowIndex;
    }
};

不知道为什么我喜欢用while多点，特别是越往后面的题目。