删除有序数组中的重复项

删除有序数组中的重复项

1.题目介绍

题目链接：LIN

本题要求是：对给定的有序数组nums删除重复元素，使得每种元素仅在该数组中出现一次，并返回新的数组长度。请注意，上述操作必须在原数组中进行(即使用O(1)空间复杂度去解决此问题)。

2.题解思路：

双指针法

给定数组是有序的，任何相同的元素均相邻。题目中介绍，这是一个非严格递增的数组，变相告诉我们该数组是有序的，因此我们可以推的该数组中所有重复元素按均相邻。

特殊情况，数组元素个数为0时返回0。nums为0，则证明没有任何元素，可以直接返回0(这点题目中没有明确说明)。

一般情况，数组元素个数大于0。一般情况下，数组中至少有一个元素，因此在删除重复元素之后也会至少剩下一个元素，因此我们可知nums[0]保持原样即可，不必修改，因为nums[0]是删除后一定存在的。因此我们从下标1处开始检查并删除元素。

快慢指针法：指定两个指针，一个fast指针(快指针)用于在数组前面遍历检查，另一个slow指针(满指针)用于把表示下一个不同元素填入指定下标位置。初始情况下，fast指向1(0处不用进行检查，因为必定不会被删除)，slow指向0。

假设数组的总长度为n，按照快慢指针法快指针将依次遍历下标1-n-1处的数字，当检查到与slow位置的值不相同时，则++slow，把该不同的数据填入到slow位置下；如果fast指针遍历到的数字与slow相同，那么我们继续fast++；

返回值：遍历结束后，我们slow指向的位置及前面所有位置均是有效数字，我们返回slow + 1即可。

3.代码示例

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        // 双指针法解答
        int slow = 0, fast = 1;//快慢指针
        while(fast < nums.size())
        {
            if(nums[fast] != nums[slow])//如果快指针对应的值不等于慢指针
            {
                nums[++slow] = nums[fast];//满指针先++，再把不同的值拷贝给nums[slow]
            }
           
           fast++;//继续遍历下一个
        }
        return slow + 1;//返回慢指针+1
    }
};