删除有序数组中的重复项（LeetCode26）

题目描述

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

示例 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 已按非严格递增排列

分析

这道题要求我们在有序数组中删除重复的元素，返回新数组的长度，并且修改原数组使其前 k 个元素为唯一元素。题目要求原地修改数组，因此不能使用额外的空间。可以使用双指针方法来解决这个问题。

• i 指针用于记录当前不重复元素的下一个位置。
• j 指针用于遍历整个数组。

初始时，i 和 j 都指向数组的第二个元素（索引1）。每当 nums[i] 与 nums[j] 不同时，将 nums[j] 赋值给 nums[i]，然后 i 向后移动一位。

代码

以下是实现该算法的 JavaScript 代码：

/**
 * @param {number[]} nums
 * @return {number}
 */
const removeDuplicates = function (nums) {
  const len = nums.length;
  if (len === 0) return 0; // 边界条件，数组为空时直接返回 0

  let i = 1; // 第一个元素总是唯一的，所以从第二个元素开始
  for (let j = 1; j < len; j++) {
    if (nums[j] !== nums[j - 1]) {
      nums[i] = nums[j];
      i++;
    }
  }
  return i; // 返回数组中唯一元素的个数
};

// 示例测试
const nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4];
console.log(removeDuplicates(nums)); // 输出: 5
console.log(nums.slice(0, 5)); // 输出: [0, 1, 2, 3, 4]

总结

在这道题中，我们使用了双指针的方法，成功地将原地数组中重复的元素删除，并返回了新数组的长度。该算法的时间复杂度为 O(n)，空间复杂度为 O(1)，满足题目对时间和空间复杂度的要求。

这道题的关键在于理解双指针的运用，并且准确地进行条件判断和指针移动。在实际编程中，这种技巧是非常常见且实用的。希望通过这篇博客，能帮助你更好地理解和掌握这一类问题的解法。