26. Remove Duplicates From Sorted Array 有序数组中去除重复项

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 by modifying the input array in-place with O(1) extra memory.

Example:

Given 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.

Difficulty: Easy

这道题让我们去除有序数组中的重复项, 可以用快慢指针记录遍历的坐标,最开始两个指针都指向第一个,如果两个指针指的数相同,则快指针向前走一步,如果不同,则两个指针都向前走一步,这样快指针走完整个数组后,慢只针对的坐标+1就是数组中不同数字的个数

解法1

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        if (nums.empty()) return 0;
        int pre = 0,cur=0,n = nums.size();
        while (cur < n)
        {
            if (nums[pre]==nums[cur]) cur++;
            else nums[++pre] = nums[cur++];
        }
        return pre + 1;
    }
};

###解法2

还是上面的思路

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