删除有序数组中的重复项-ii

Tips

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

相关题目:

• 26. 删除排序数组中的重复项
• 27. 移除元素

题目

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

提示:

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

示例

输入: nums = [1, 1, 1, 2, 2, 3]
输出: 5, nums = [1, 1, 2, 2, 3]
解释: 函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3. 不需要考虑数组中超出新长度后面的元素.

输入: nums = [0, 0, 1, 1, 1, 1, 2, 3, 3]
输出: 7, nums = [0, 0, 1, 1, 2, 3, 3]
解释: 函数应返回新长度 length = 7, 并且原数组的前五个元素被修改为 0, 0, 1, 1, 2, 3, 3. 不需要考虑数组中超出新长度后面的元素.

题解

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var removeDuplicates = function (nums) {
  const n = nums.length
  if (n <= 2) return n

  // 数组的前两个数必然可以被保留
  let slow = 2
  let fast = 2

  while (fast < n) {
    // 检查上上个应该被保留的元素 nums[slow - 2] 是否和当前待检查元素 nums[fast] 相同
    if (nums[slow - 2] !== nums[fast]) {
      nums[slow] = nums[fast]
      slow++
    }

    fast++
  }

  return slow
}

Rust

pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
    let n = nums.len();
    if n <= 2 {
        return n as i32;
    }

    let (mut slow, mut fast) = (2, 2);
    while fast < n {
        if nums[slow - 2] != nums[fast] {
            nums[slow] = nums[fast];
            slow += 1;
        }

        fast += 1;
    }

    slow as i32
}