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