Cinte's Leetcode Record
0%

27. 移除元素

Posted on Edited on In Disqus:
Symbols count in article: 821 Reading time ≈ 1 mins.

27. 移除元素

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int pt = 0;
        for(auto& num : nums)
            if(num != val)
                nums[pt++] = num;
        return pt;
    }
};

最坏情况下,pt也需要同时遍历一遍nums

考虑到题目中说元素的顺序可以改变，所以针对这一个条件进行优化

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 left = 0, right = nums.size(); // right需要设定为size而不是size-1,否则当只有一个数字时候不会进入循环
        // right比原来大一可以让left多走一步
        while(left < right)
        {
            if(nums[left] == val)
                nums[left] = nums[right-- - 1];
            else
                ++left;
        }
        return left;
    }
};

review

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) {
        if(nums.empty())
            return 0;
        int n = nums.size();
        int i = 0, j = n - 1;
        while(i <= j)
        {
            while(i <= j && nums[i] == val)
                swap(nums[i], nums[j--]);
            ++i;
        }
        return j + 1;
    }
};