0080. 删除排序数组中的重复项 II Remove Duplicates from Sorted Array II

问题描述

先分析这个题的条件:

  • 数组是有序的, 有重复元素
  • 原地移除部分重复元素, 每个重复的数值最多只能出现两次
  • 要保持原先的顺序
  • 空间复杂度是 O(1)

快慢型双指针

典型的快慢型双指针问题.

其中, 快指针用于遍历数组; 慢指针用于移除重复元素后, 指向数组的最高位.

fast-slow two-pointers

#![allow(unused)]
fn main() {
// 快慢型双指针
pub fn remove_duplicates1(nums: &mut Vec<i32>) -> i32 {
    assert!(!nums.is_empty());
    let len = nums.len();

    // 慢指针指向结果数组的最高位
    let mut slow = 0;
    // 用快指针遍历数组
    let mut fast = 0;

    // 遍历数组
    while fast < len {
        let curr = nums[fast];
        // 元素重复的次数
        let mut dup = 0;

        // 复制前两个重复的元素, 而忽略后面的.
        while (fast < len) && (curr == nums[fast]) {
            if dup < 2 {
                nums[slow] = curr;
                // 同时移动慢指针, 结果数组最高位 +1
                slow += 1;
            }
            dup += 1;
            fast += 1;
        }
    }

    slow as i32
}
}

优先双指针

这里的优化仅仅是简化了思路, 但是性能并不一定更好.

simplify-two-pointers

#![allow(unused)]
fn main() {
// 优化双指针
pub fn remove_duplicates2(nums: &mut Vec<i32>) -> i32 {
    assert!(!nums.is_empty());
    let len = nums.len();
    if len < 3 {
        return len as i32;
    }

    // 慢指针指向结果数组的最高位, 跳过前两个元素
    let mut slow = 2;

    // 用快指针遍历数组, 跳过前两个元素
    for fast in 2..len {
        // 这里是关键点!
        // `slow - 2` 表示允许有两个重复的元素.
        if nums[fast] != nums[slow - 2] {
            // 移动慢指针
            nums[slow] = nums[fast];
            slow += 1;
        }
    }

    slow as i32
}
}

相关问题