剑指leetcode—删除重复排序数组中的重复项

题目描述：给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

算法一
双指针法
算法
数组完成排序后，我们可以放置两个指针 i和 j，其中 i 是慢指针，而 j 是快指针。只要 nums[i]=nums[j]我们就增加j以跳过重复项。当我们遇到 nums[j]≠nums[i]时，跳过重复项的运行已经结束，因此我们必须把它（nums[j]）的值复制到 nums[i+1]。然后递增 i，接着我们将再次重复相同的过程，直到 j 到达数组的末尾为止。
java实现

class Solution {
    public int removeDuplicates(int[] nums) {
        int p=0;//慢指针
        int q;//快指针
        for(q=1;q<nums.length;q++)
        {
            if(nums[q]!=nums[p])
            {                       
                nums[p+1]=nums[q];
            }
            p++；
        }
            return p+1;
    }
}

根据上面的思路很容易实现c语言

算法优化

考虑这样的情况，如果数组中没有重复的元素，按照上面的方法，每次比较nums[p]和nums[q]不同时，会将q指向的元素原地复制一遍，这个操作是没有必要的。
因此我们还可以添加一个小小的判断，当q-p>1,才会进行复制。

class Solution {
    public int removeDuplicates(int[] nums) {
        int p=0;//慢指针
        int q;//快指针
        for(q=1;q<nums.length;q++)
        {
            if(nums[q]!=nums[p])
           {
               if(q-p>1)
               {              
                nums[p+1]=nums[q];
                }              
                p++;
            }
        }
            return p+1;
    }
}