LC26. 删除有序数组中的重复项

题目描述

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。 由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。 将最终结果插入 nums 的前 k 个位置后返回 k 。 不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。 判题标准: 系统会用下面的代码来测试你的题解: 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： 输入：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 * 10^4 -10^4 <= nums[i] <= 10^4 nums 已按 升序 排列

题目解析

题目在说什么

这道题给你一个已经排好序（从小到大）的数组，比如 [1,1,2]。里面有些数字重复出现了，你要把重复的删掉，只留一个。而且不能新建一个数组，只能在原来的数组上动手脚（这叫“原地”修改）。最后，你要返回新数组的长度，比如 [1,1,2] 去重后变成 [1,2]，长度就是 2。注意，数组后面的位置可以不管，比如 [1,2,_] 下划线表示随便是什么，我们只看前两个位置。

思路是怎么来的

想象你在整理一排书架，书是按编号从小到大排好的。有些编号重复了，比如好几本编号都是 1。你想只留一本编号 1，然后把后面的书往前挪，让书架前面全是唯一的编号。

怎么做到呢？你可以用两个手指头：

• 一个手指（叫 i）从头到尾扫过每一本书，看看这本书是不是新的编号。
• 另一个手指（叫 j）指着“下一个空位”，也就是你应该把新书放哪里。

一开始，j 指着第一个位置。你从第一本书开始看：

• 第一本书肯定是新的（因为还没看过），所以你把它放到 j 指的位置（就是第一个位置），然后 j 移到下一个空位。
• 接着看第二本书：如果它和前面那本编号一样，说明重复了，跳过它，不处理。
• 如果它和前面那本不一样，说明是新编号，就把它放到 j 指的位置，然后 j 再往后移。

这样，j 始终指着“下一个该放新书的位置”，而 i 负责找新书。最后，j 的值就是去重后数组的长度，因为前面 j 个位置都放好了唯一的书。

代码逐步拆解

我们来看参考代码（Java），一行一行解释：

public int removeDuplicates(int[] nums) {
    int n = nums.length;          // 数组的长度，比如 [1,1,2] 长度是 3
    int j = 0;                    // j 指向“下一个要放新元素的位置”，一开始是 0（第一个位置）

    for (int i = 0; i < n; i++) { // i 从 0 到 n-1，遍历每个元素
        // 判断当前元素是不是“新元素”
        // 条件：要么是第一个元素（i==0），要么和前面一个元素不同（nums[i] != nums[i-1]）
        if (i == 0 || nums[i] != nums[i-1]) {
            // 如果是新元素，就把它放到 j 指向的位置
            nums[j] = nums[i];
            // 然后 j 往后移动一位，准备放下一个新元素
            j++;
        }
        // 如果是重复元素，什么也不做，i 继续往后走
    }