LeetCode27 移除元素

前言

题目： 27.移除元素
文档： 代码随想录——移除元素
编程语言： C++
解题状态： 错误，代码组织不严谨。

思路

C++数组中的元素在内存地址上是连续的，不能真正地被移除，只能覆盖，因此只能考虑覆盖的方法。

代码

方法一： 暴力解法

暴力解题，第一个for循环遍历数组，第二个for循环更新数组。

时间复杂度：$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--;
                size--;
            }
        }

        return size;
    }
};

方法二： 双指针法

通过一个快指针和一个慢指针在一个循环内完成两个循环的工作。

时间复杂度：$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 (nums[fastIndex] != val) {
                nums[slowIndex++] = nums[fastIndex];
            }
        }

        return slowIndex;
    }
};