删除排序数组中的重复项

    数组 双指针

    题目描述

    给定一个已排序的数组 nums，你需要 原地 删除重复出现的元素，使得每个元素只出现一次，并返回移除后数组的新长度。

    不要使用额外的数组空间，你必须在 原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

    思路分析

    由于数组是 已排序 的，重复的元素一定会相邻。我们可以利用这一特性，使用 双指针（快慢指针）法来解决。

    • 慢指针 (slow)：指向当前已确定的不重复序列的最后一个元素。
    • 快指针 (fast)：从第二个元素开始遍历整个数组，寻找与慢指针指向的元素不同的新值。

    算法步骤

    1. 初始化：如果数组为空或长度为 0，直接返回 0。否则，设置 slow = 0。
    2. 遍历：快指针 fast 从 1 开始遍历到数组末尾。
    3. 比较：
      • 如果 nums[fast] !== nums[slow]，说明找到了一个新的不重复元素。
      • 此时将 slow 向后移动一位 (slow++)。
      • 将 nums[fast] 的值赋给 nums[slow]。
    4. 结束：遍历完成后，slow + 1 即为不重复元素的个数（因为索引从 0 开始）。

    示例代码

    /**
 * 移除排序数组中的重复项，并返回新长度。
 * 注意：必须在“原地”修改输入数组，并在使用 O(1) 额外空间的条件下完成。
 * 
 * @param {number[]} nums - 已排序的整数数组
 * @returns {number} - 去重后数组的新长度
 */
export function removeDuplicates(nums) {
  // 基础边界检查：如果 nums 不是有效的数组或长度为 0，直接返回长度 0
  if (!nums || !Array.isArray(nums) || nums.length === 0) {
    return 0;
  }

  // 使用双指针法：
  // slow (慢指针)：记录当前已确定的不重复序列的最后一个元素的位置
  let slow = 0;

  // fast (快指针)：遍历整个数组，寻找与 slow 指向的元素不同的新值
  for (let fast = 1; fast < nums.length; fast++) {
    // 如果快指针发现了一个与当前 slow 指向的值不同的新元素
    if (nums[fast] !== nums[slow]) {
      // 慢指针后移一位，为存放新元素腾出空间
      slow++;
      // 将新元素覆盖到慢指针当前指向的位置
      nums[slow] = nums[fast];
    }
    // 如果 nums[fast] 等于 nums[slow]，说明是重复项，快指针跳过
  }

  // 由于数组下标从 0 开始，长度应为最后一位下标 + 1
  return slow + 1;
}

// 示例调用
const nums1 = [1, 1, 2];
const len1 = removeDuplicates(nums1);
console.log(len1, nums1.slice(0, len1)); // Expected: 2, [1, 2]

const nums2 = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4];
const len2 = removeDuplicates(nums2);
console.log(len2, nums2.slice(0, len2)); // Expected: 5, [0, 1, 2, 3, 4]

    复杂度分析

    • 时间复杂度：O(n)，其中 n 是数组的长度。我们只需要遍历一遍数组。
    • 空间复杂度：O(1)，我们只使用了两个额外的索引变量。