LeetCode NO.26 从数组中删除重复项

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

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

示例 1：

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

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

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

示例2：

给定 nums = [0,0,1,1,1,2,2,3,3,4],

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

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

分析-双指针法

这里有一个很容易观察到的利用点，就是 排序数组，对于一个排序数组来说，所有重复的元素，都是彼此连续排列的，如果按顺序遍历，那么只需要顺序检查逐个元素的下一个位置是否是一样的元素即可判断元素是否重复。

逐个遍历，意味着我们不需要额外的空间来保存元素。不管问题规模大小，只需要一个指针，即空间复杂度为 O(1)。

这个解法对空间的要求很低。需要理解的是这个指针的功能：用于标识整理后的数组的有效位。甚至可以理解为这里有两个指针，一个是新增指针 index，另一个是循环参数 i。都作用于入参数组 nums[]。即 双指针法

class Solution {
    public static int removeDuplicates(int[] nums) {
        if(nums.length == 0)
            return 0;
        if(nums.length == 1)
            return 1;
        int index = 0;//用于重复检查的索引，也是新数组的长度
        for (int i = 1; i < nums.length; i++) {
            if (nums[index] != nums[i]) {
                // 类似于在有序的卡牌上剔除重复卡牌
                nums[++index] = nums[i];
            }
        }
        return index + 1;
    }
}

算法流程分析：示例入参：nums = [1,2,2,3,4]，整理后的结果：nums = [1,2,3,4]

26.png