04-删除有序数组中的重复项

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

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

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

方法一 

function removeDuplicates(nums: number[]): number {if (nums.length === 0) {return 0;}// 初始化慢指针，指向第一个元素let slow = 0;// 快指针从第二个元素开始遍历数组for (let fast = 1; fast < nums.length; fast++) {if (nums[fast]!== nums[slow]) {// 当快指针指向的元素与慢指针指向的元素不同时// 慢指针前进一位slow++;// 将快指针指向的元素赋值给慢指针指向的位置nums[slow] = nums[fast];}}// 慢指针加 1 即为不重复元素的数量return slow + 1;
}// 示例调用
const nums = [1, 1, 2];
const k = removeDuplicates(nums);
console.log("不重复元素的数量:", k);
console.log("去重后的数组前 k 个元素:", nums.slice(0, k));

代码解释

1. 边界条件检查：

   • 如果数组 nums 的长度为 0，直接返回 0，因为没有元素需要处理。

2. 初始化指针：

   • slow 指针初始化为 0，用于标记不重复元素的位置。
   • fast 指针初始化为 1，用于遍历数组。

3. 遍历数组：

   • 使用 for 循环，让 fast 指针从数组的第二个元素开始遍历。
   • 当 nums[fast] 不等于 nums[slow] 时，说明遇到了一个新的不重复元素。
   • 将 slow 指针向后移动一位，并将 nums[fast] 的值赋给 nums[slow]。

4. 返回结果：

   • 遍历结束后，slow + 1 就是不重复元素的数量，将其返回。

复杂度分析

• 时间复杂度：\(O(n)\)，其中 \(n\) 是数组的长度。只需要遍历数组一次。
• 空间复杂度：\(O(1)\)，只使用了常数级的额外空间。

这种双指针法的思路是，slow 指针用于记录不重复元素的位置，fast 指针用于遍历数组，当遇到不重复元素时，将其放到 slow 指针指向的位置。这样可以在不使用额外空间的情况下，原地删除重复元素。

其他方法（拓展一下，但是不复合题意）

1. 使用 Set 进行去重

Set 是 JavaScript 中一种数据结构，它只会存储唯一的值。以下是使用 Set 去重的示例代码：

function nonInPlaceRemoveDuplicates(nums: number[]): number[] {return [...new Set(nums)];
}const nums = [1, 1, 2, 2, 3];
const result = nonInPlaceRemoveDuplicates(nums);
console.log(result); 

在这个例子中，代码将数组 nums 转换为 Set 来去除重复元素，然后再将 Set 转换回数组。但这里的问题是，它创建了一个新的数组，并没有对原数组进行原地修改，不符合本题的要求。

 2. 使用 filter 方法去重

function nonInPlaceRemoveDuplicatesByFilter(nums: number[]): number[] {return nums.filter((value, index, self) => {return self.indexOf(value) === index;});
}const nums2 = [1, 1, 2, 2, 3];
const result2 = nonInPlaceRemoveDuplicatesByFilter(nums2);
console.log(result2); 

同样，filter 方法会返回一个新的数组，原数组 nums 不会被修改，也不满足本题原地修改的条件。