LeetCode 27. 移除元素

作者: SmallRookie | 来源:发表于2018-12-06 00:51 被阅读0次

    题目描述

    题解

    简单方法

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

    时间复杂度为O(n),空间复杂度为O(1)

    双指针法

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

    时间复杂度为O(n),空间复杂度为O(1)

    双指针 —— 当要删除的元素很少时

    class Solution {
    public:
        int removeElement(vector<int>& nums, int val) {
            int i = 0;
            int n = nums.size();
            while(i < n) {
                if(nums[i] == val) {
                    nums[i] = nums[n-1];
                    n--;
                }
                else i++;
            }
            return n;
        }
    };
    

    时间复杂度为O(n),空间复杂度为O(1)

    相关文章

      网友评论

        本文标题:LeetCode 27. 移除元素

        本文链接:https://www.haomeiwen.com/subject/daogcqtx.html