Skip to main content

删除排序数组中的重复项

Tips

题目类型: 数组, 快慢指针

相关题目:

题目​

给你一个按升序的排列数组 nums, 请你原地删除重复出现的元素, 使每个元素只出现一次, 返回删除后数组的新长度. 不要使用额外的数组空间, 你必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成.

提示:
  • 1 <= nums.length <= 3 * 10⁴
  • -10⁴ <= nums[i] <= 10⁴
  • nums 已按升序排列
示例

输入: nums = [1, 1, 2]

输出: 2, 其中 nums 变成 [1, 2, 2]

题解​

看到有序数组, 先想到双指针, 这道题可以使用快慢指针: 让慢指针 slow 走在后面, 快指针 fast 走在前面探路, 找到一个不重复的元素就告诉 slow 并让 slow 前进一步. 这样当 fast 指针遍历完整个数组 nums 后, 前 slow + 1 个就是不重复元素.

  • 第零步: fast, slow 都指向第一个元素;
  • 第一步: fast, slow 指向的都是 1, 因此只需 fast 向前走一步;
  • 第二步: 此时 fast, slow 指向的值不同, 让 slow + 1, 并把 fast 指向的值赋值给 slow 指向的值, 然后 fast 向前走一步;
  • 第三步: fast, slow 指向的都是 2, 因此只需 fast 向前走一步;
  • 第四步: fast, slow 指向的都是 2, 因此只需 fast 向前走一步;
  • 第五步: 此时 fast, slow 指向的值不同, 让 slow + 1, 并把 fast 指向的值赋值给 slow 指向的值, 然后 fast 向前走一步;
  • 第六步: fast, slow 指向的都是 3, 因此只需 fast 向前走一步, 此时 fast > n, 跳出循环, 返回 show + 1 即可.
fast              fast              fast              fast              fast              fast              fast
 ↓                 ↓                 ↓                 ↓                 ↓                 ↓                 ↓
[1 2 2 2 3 3]   [1 2 2 2 3 3]   [1 2 2 2 3 3]   [1 2 2 2 3 3]   [1 2 2 2 3 3]   [1 2 3 2 3 3]   [1 2 3 2 3 3]
 ↑               ↑                 ↑               ↑               ↑                 ↑               ↑
slow            slow              slow            slow            slow              slow            slow
/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
  const n = nums.length

  // 双指针
  let slow = 1,
    fast = 1

  while (fast < n) {
    if (nums[slow - 1] !== nums[fast]) {
      nums[slow] = nums[fast]
      slow++
    }

    fast++
  }

  return slow
}