【LeetCode】26. Remove Duplicates from Sorted Array （删除排序数组中的重复项）-C++实现的两种方法

问题描述：

一、第一种解题方法

（1）双指针法

（2）数组完成排序后，我们可以放置两个指针 i和 j，其中 i是慢指针，而 j 是快指针。

 只要 nums[i] = nums[j]，我们就增加 j 以跳过重复项。

（3）当我们遇到 nums[j]≠nums[i] 时，跳过重复项的运行已经结束，

因此我们必须把它（nums[j]）的值复制到 nums[i + 1]。然后递增 i，

 

接着我们将再次重复相同的过程，直到 j到达数组的末尾为止。

（4）完整实现代码：

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

二、第二种解题方法

（1）建立一个函数，找出下一个不等元素的下标

    int nextDifferentCharacterIndex(const vector<int> &nums, int p){
        for( ; p < nums.size() ; p ++ )
            if( nums[p] != nums[p - 1] )
                break;
        return p;
    }

因为 nums[p] = nums[p - 1] ，则p++

这时，nums[p] != nums[p - 1] ，

return p = 2;

所以index = 2;

（2）先给大家附上代码：

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {

        if(nums.size() == 0)  //保证数组的长度不为0
            return 0;

        int res = 1;  //计数：不相等的元素个数
        int index = nextDifferentCharacterIndex(nums, 1);
        int i = 1;
        while(index < nums.size()){
            res ++;
            nums[i] = nums[index];
			i++；
			index++;
            index = nextDifferentCharacterIndex(nums, index);
        }

        return res;
    }

private:
    int nextDifferentCharacterIndex(const vector<int> &nums, int p){
        for( ; p < nums.size() ; p ++ )
            if( nums[p] != nums[p - 1] )
                break;
        return p;
    }
};

（3）

（4）这时，nums[p] != nums[p - 1]

所以：

nums[i] = nums[index];

（5）然后 i++，index++

 （6）然后，重复 index = nextDifferentCharacterIndex(nums, index);

（7）复杂度

Time Complexity:  O(n)
Space Complexity: O(1)

 

参考资料：

1.https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array/solution/

2.https://github.com/liuyubobobo/Play-Leetcode