删除排序数组中的重复项

Tips

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

相关题目:

• 27. 移除元素
• 61. 旋转链表
• 80. 删除有序数组中的重复项-ii
• 83. 删除排序链表中的重复元素
• 141. 环形链表
• 142. 环形链表 II
• 234. 回文链表

题目

给你一个按升序的排列数组 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 个就是不重复元素.

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
  let slow = 0

  for (let fast = 1; fast < nums.length; fast++) {
    if (nums[fast] !== nums[slow]) {
      slow++
      nums[slow] = nums[fast]
    }
  }

  return slow + 1
}

Rust

pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
    let mut slow = 0;

    for fast in 1..(nums.len()) {
        if (nums[fast] != nums[slow]) {
            slow += 1;
            nums[slow] = nums[fast];
        }
    }

    slow as i32 + 1
}