计算机科学基础leetcode刷题数组
,
Source
Edit
History

27. 移除元素

Problem: 27. 移除元素

思路

第一想法暴力破解,一个循环遍历,一个循环数组前移,一个变量length记录数组的size

解题方法

暴力破解就不讲了

主要讲解快慢指针,想象快指针指向旧数组,慢指针指向新数组,

==快指针的作用是筛选需要的元素==,跳过需不要的元素

由题意得知新数组不需要 num[i] == value 的值,于是遍历时跳过该value,并且将旧数组的值指向新数组

脑瘫的错误

在暴力破解中内循环写成nums[i] = nums[i + 1];内循环指针是j

for循环范围写错成了for(int i = 0; i < length - 1; i++)

复杂度

  • 时间复杂度:

$O(n)$

  • 空间复杂度:

$O(1)$

Code

暴力算法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int length = nums.size();
        for(int i = 0; i < length; i++){
            if(nums[i] == val) {
                for(int j = i; j < length - 1;j++) {
                    nums[j] = nums[j + 1];
                }
                i--;
                length--;
            }
        }
        return length;
    }
};

快慢指针法

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int slow = 0;
        int fast = 0;
        while(fast < nums.size()) {
            if(nums[fast] != val) { //不等于val 保存
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int fast = 0,slow = 0;
        while(fast < nums.size()) {
            if(nums[fast] == val) { //跳过不需要
                fast++; continue;
            }
            nums[slow++] = nums[fast++];
        }
        return slow;
    }
};