算法题–LeetCode26.删除排序数组中的重复项

题目简介

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

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。

解题思路

这里要重点注意是：排序数组 数组是已经排好顺序的，不会出现跨过一些不同数会与当前数相同的情况。（这一点一开始自己没注意，写的算法十分的复杂，最后发现是自己审题失误）

重新来分析题意：
给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
也就是说数组可能长这样

1
2
3

1 1 | 2 2 2 2 | 3 3 | 4 | 5 5 5 5 | 6

竖杠是为了更好地理解后面的算法

看到这个我想你应该大概有点感觉了，我们需要一个指针指向一堆相同数字第一个的位置，另一个指针往后动，当第二个指针前一个值和它自己对应的值不相同时，换句话说它处在两个相同数字堆的交界处，将第二个指针对应的值赋给第一个指针，与此同时第一个指针后移。

重点：整体过程是一个将两个相同数字堆的交界处的数字存在数组前面的一个过程，整个过程第一个指针只有在第二个指针位于交界处时才会后移，而第二个指针是不断后移的。

AC代码（Java）

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums.length == 0) return 0;
        else{
            int index = 1;
            for(int i = 1;i < nums.length;i++){
                if(nums[i]!=nums[i-1]){
                    nums[index++] = nums[i];
                }
            }
        return index;
        }
    }
}

index是上文所述的指针1，i 就是常速指针，也就是指针2。