关关的刷题日记08 – Leetcode 26. Remove Duplicates from Sorted Array 方法2、3

题目

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length. Do not allocate extra space for another array, you must do this in place with constant memory. For example, Given input array nums = [1,1,2], Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

方法2：遍历数组，遇到重复元素直接删掉。最后得到的数组的长度就是返回值。时间复杂度O(n2), 每次vector erase的代价都是O(n).

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        for(int i=1; i<nums.size(); i++)
        {
            if(nums[i]==nums[i-1])
            {
                nums.erase(nums.begin()+i);
                i--;
            }
        }
        return nums.size();
    }
};

方法3：遍历数组，出现不相等元素就将该元素陆续存到数组的前面，j为数组下标。就在原数组上面改，之所以可以这么处理，因为j是肯定跑不过i的。时间复杂度O(n). [aabccd] its index as i [abcd] its index as j

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

人生易老，唯有陪伴最长情，加油！

以上就是关关关于这道题的总结经验，希望大家能够理解，有什么问题可以在我们的专知公众号平台上交流或者加我们的QQ专知-人工智能交流群 426491390，也可以加入专知——Leetcode刷题交流群（请先加微信小助手weixinhao: Rancho_Fang）。 同时请，关注我们的公众号，获取最新关于专知以及人工智能的资讯、技术、算法等内容。扫一扫下方关注我们的微信公众号。