SlovinG
Search K

Appearance

26.删除有序数据中的重复项 ​

难度：简单

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

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

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

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [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]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

提示：

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

解题思路 ​

由于原数组按照升序排列，所以可以跟 27 题一个思路，采用快慢指针法。

将快指针和慢指针指向的元素进行逐个比对，每当二者的值不相同时，慢指针前进一位，并将快指针指向元素值赋给慢指针指向的位置。

我的代码 ​

java
public int removeDuplicates(int[] nums) {
    int ln = nums.length;
    int slowIndex = 0;
    int fastIndex = 0;
    while (fastIndex < ln) {
        if (nums[fastIndex] != nums[slowIndex]) {
            slowIndex++;
            nums[slowIndex] = nums[fastIndex];
        }
        fastIndex++;
    }
    return slowIndex + 1;
}

时间复杂度：O(n)

空间复杂度：O(1)

最后返回的时候，慢指针要+1，这样才是新数组真正的长度。

通用解法 ​

为了让解法更具有一般性，我们将原问题的「最多保留 1 位」修改为「最多保留 k 位」。

对于此类问题，我们应该进行如下考虑：

  • 由于是保留 k 个相同数字，对于前 k 个数字，我们可以直接保留。
  • 对于后面的任意数字，能够保留的条件是：若该数字与当前欲写入位置前面的倒数第 k 个元素值不相同则保留。因为这说明了该数字的重复次数并没有超过 k 次。

例如，假设我们令 k = 2，有样例：[3, 3, 3, 3, 4, 4, 4, 5, 5, 5]，那么代码思路为：

  1. 设定指针 slowIndex，指向待插入位置，slowIndex 初始值为 0，目标数组当前为 []

  2. 首先我们先让前 k 位直接保留。slowIndex 变为 2，目标数组为 [3, 3]

  3. 继续往后遍历，能够保留的前提是与 slowIndex 的前面倒数第 k 位元素不同，因此我们会跳过剩余的 3，将第一个 4 追加进去。slowIndex 变为 3，目标数组为 [3, 3, 4]

  4. 继续上述过程，追加第二个 4，slowIndex 变为 4，目标数组为 [3, 3, 4, 4]

  5. 当整个数组被扫描完，最终我们得到了目标数组 [3, 3, 4, 4, 5, 5] 和答案 slowIndex 为 6。

代码展示 ​

java
public int removeDuplicates(int[] nums) {
    return process(nums, 1);
}

int process(int[] nums, int k) {
    int ln = nums.length;
    int slowIndex = 0;
    int fastIndex = 0;
    while (fastIndex < ln) {
        if (slowIndex < k || nums[slowIndex - k] != nums[fastIndex]) {
            nums[slowIndex] = nums[fastIndex];
            slowIndex++;
        }
        fastIndex++;
    }
    return slowIndex;
}

时间复杂度：O(n)

空间复杂度：O(1)

总结 ​

当问题的条件是 数组有序 且要求 部分元素保留 的时候，可以考虑使用双指针法。

通用解法 是一种针对 数据有序，相同元素最多保留 k 位 问题更加本质的解法，该解法是从性质出发提炼的，利用了 数组有序 和 保留逻辑 两大主要性质。