LeetCode 26. 删除排序数组中的重复项（简单题）

1.题目描述：

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。
不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。
链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array

2.题解思路：

注意到数组是有序的，所以重复的元素一定是相邻的。

题目要求在原地删除重复出现的元素，其实就是将后边不重复的元素移动到前边，替代那些重复的元素。

也就是说，遇到重复元素不做处理，遇到不重复元素才往前覆盖。

可以考虑使用双指针法（快慢指针）。快指针从第二个元素开始（下标1）遍历数组中所有的元素，慢指针指向最后一个不重复的元素（初始为下标0）。

当快指针j指向的值和慢指针i指向的值相等时，说明快指针指向的是重复元素，所以慢指针不动（因为下一个就是重复元素了，而慢指针指向的是不重复元素），快指针自增。

当快指针j指向的值和慢指针i指向的值不相等时，说明快指针指向的是不重复元素，需要将这个不重复元素覆盖到第一个重复元素的位置（也就是慢指针的下一个位置），再将快指针自增。

3.代码实现：

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

复杂度分析：

• 时间复杂度：O(n)，假设数组的长度是n，需要遍历n步。
• 空间复杂度：O(1)，不需要额外开辟新的空间。