LeetCode 删除有序数组中的重复项

题目描述

给你一个 非严格递增排列 的数组 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 。不需要考虑数组中超出新长度后面的元素。

解题思路

为方便描述，把 nums 记作 a。

示例 2 的 a=[0,0,1,1,1,2,2,3,3,4]。

首先 a[0]=0 肯定要保留，我们从 a[1]开始讨论：

• 如果 a[1]=a[0]，那么 a[1]是重复项，不保留。
• 如果a[1]≠a[0]，那么 a[1]不是重复项，保留。

具体算法如下：

1. 初始化 k=1，表示保留的元素要填入的下标。
2. 从 i=1 开始遍历 nums。
3. 如果 nums[i]=nums[i−1]，那么 nums[i] 是重复项，不保留。
4. 如果 nums[i]≠nums[i−1]，那么 nums[i] 不是重复项，保留，填入 nums[k] 中，然后把 k加1。
5. 遍历结束后，k 就是 nums 中的唯一元素的数量，返回 k。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function(nums) {
    let k = 1;
    for (let i = 1; i < nums.length; i++) {
        if (nums[i] != nums[i - 1]) { // nums[i] 不是重复项
            nums[k++] = nums[i]; // 保留 nums[i]
        }
    }
    return k;
};

代码解释

这段代码是一个JavaScript函数，其目的是从一个整数数组nums中去除连续的重复元素，并返回不重复元素的数量。注意是不需要考虑数组中超出新长度后面的元素

下面是逐行分析：

1. var removeDuplicates = function(nums) { ... };

   • 定义了一个名为removeDuplicates的函数，它接收一个数组nums作为参数。

2. let k = 1;

   • 声明一个变量k并初始化为1。这个变量用于记录不重复元素的索引位置。

3. for (let i = 1; i < nums.length; i++) { ... }

   • 开始一个循环，从数组的第二个元素开始遍历，即i=1，直到数组的最后一个元素。

4. if (nums[i] != nums[i - 1]) { ... }

   • 如果当前元素nums[i]与前一个元素nums[i - 1]不相等，说明当前元素不是重复项。

5. nums[k++] = nums[i];

   • 将当前元素nums[i]复制到索引k的位置，并将k的值加1。这样，不重复的元素会被移动到数组的前面。

6. return k;

   • 循环结束后，返回k的值，即不重复元素的数量。

代码技巧点：

（一）
k++不是1。k++是一个后缀增量操作符，这意味着它会增加变量k的值，但表达式的结果是变量k增加之前的值。所以，当k的初始值是1时，执行k++后，k将变成2，但表达式k++的结果是1。

让我们通过代码来说明这一点：

let k = 1; // 初始化k为1
let result = k++; // 此时result是1，k的值变为2
console.log(result); // 输出: 1
console.log(k); // 输出: 2

在上面的代码中，k++首先使用k的原始值1进行操作，然后将k的值增加到2。因此，result变量存储的是k增加之前的值1。

回到你提到的nums[k++] = nums[i];这行代码，当k的初始值是1时：

• 第一次执行这行代码时，nums[k]将被赋值为nums[i]，此时k的值是1，所以nums[1]被赋值。
• 赋值操作完成后，k的值增加1，变为2。

（二）
函数只是将不重复的元素复制到的数组的前面了，实际上还是操作的原数组，所以后面不参与复制同时没有被覆盖的元素会保留在原来的位置，运行依旧正确。