LeetCode-26. 删除有序数组中的重复项(Java)

这是我在51CTO博客开启的写作之路，第一次正式写博客记录我在LeetCode的刷题日，希望能帮助更多的小伙伴攻面自己心仪的公司offer。

如下对于 LeetCode-26. 删除有序数组中的重复项，进行全面解析并小结解题思路，同学们请参考：

1.题目描述

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。

考虑 nums 的唯一元素的数量为 k ，你需要做以下事情确保你的题解可以被通过：

• 更改数组 nums ，使 nums 的前 k 个元素包含唯一元素，并按照它们最初在 nums 中出现的顺序排列。nums 的其余元素与 nums 的大小不重要。
• 返回 k 。

判题标准:

系统会用下面的代码来测试你的题解:

int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案

int k = removeDuplicates(nums); // 调用

assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

如果所有断言都通过，那么您的题解将被 通过。

示例 1：

2
1
2 
。

示例 2：

5
0
1
2
3
4

提示：

• 1 <= nums.length <= 3 * 104
• -104 <= nums[i] <= 104
• nums 已按 升序 排列

2.思路分析

这道题目的要求是：对给定的有序数组 nums 删除重复元素，在删除重复元素之后，每个元素只出现一次，并返回新的长度，上述操作必须通过原地修改数组的方法，使用 O(1) 的空间复杂度完成。

这里采用双指针解法：一个指针 i 进行数组遍历，另外一个指针 j 指向有效数组的最后一个位置。只有当 i 所指向的值和 j 不一致（不重复），才将 i 的值添加到 j 的下一位置。

3.算法实现

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

4.复杂度分析

如下是本次算法的复杂度分析：

时间复杂度：O(n)，其中 n 是数组的长度。快指针和慢指针最多各移动 n 次。

空间复杂度：O(1)。只需要使用常数的额外空间。

5.小结

其实可以看作一个喜新厌旧的人的一个排队列过程。这个人比较喜新厌旧，看到没有见过的数字，就把它按顺序从左到右排好，如果是已经见过的数字就直接忽略掉。 比如0 4 4 7 7 7 9 第一个数字保持不动。 然后往后面看看到第一个4，没见过，是第一次看到4，于是把它排到0的后面。 再往后看，又看到一个数字4，老面孔直接忽略掉。 再往后看看到一个数字7，是新面孔。于是把她拉到最左边，放在紧跟着0 4的位置。 再往后看是7，直接忽略，接着又是7，直接忽略。 直到看到新的数字9，然后把然后把放到0 4 7的后面。 可以理解为左边是所有的新面孔的队列，而快指针就是评审官，负责找到新面孔。

这么理解的话去看很多人的代码和解释，我觉得会更容易理解一些。