删除有序数组中的重复项

题目描述

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

示例

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4,_,_,_,_,_]

我的解题过程

解题思路:双指针法

这道题要求原地删除重复元素，关键是理解”原地”的含义——不能使用额外的数组空间，只能在原数组上操作。

既然数组是有序的（非严格递增），那么重复的元素一定是连续的。可以用双指针来解决：

• left 指针遍历整个数组，用来读取元素
• right 指针指向当前不重复元素应该放置的位置，用来写入元素
• 当 nums[left] 和 nums[left + 1] 不相同时，说明 left 指向的是当前这个数字的最后一次出现，此时把它写入 right 位置

这样遍历一遍后，right 的值就是新数组的长度，且前 right 个元素就是去重后的结果。

function removeDuplicates(nums: number[]): number {
  let left = 0,
    right = 0;

  while (left < nums.length) {
    if (nums[left] !== nums[left + 1]) {
      nums[right] = nums[left];
      right++;
    }
    left++;
  }

  return right;
}

小结

双指针是处理数组原地修改问题的经典方法。这道题的核心在于：

• 利用数组已排序的特性，重复元素必然相邻
• 用 left 遍历，用 right 记录写入位置
• 只在遇到不重复元素时才写入

时间复杂度 O(n)，空间复杂度 O(1)，符合题目要求。