leetcode打卡-0080删除有序数组中的重复项II

19 4月 2021
3 分钟阅读
标签:
leetcode,
算法,
数组,
Python,
Rust

题目描述

给你一个有序数组nums，请你原地删除重复出现的元素，使每个元素最多出现两次，返回删除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用O(1)额外空间的条件下完成。

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/remove-duplicates-from-sorted-array-ii

解题思路

1. 通用套路

这题和leetcode第26题-删除数组中重复数，几乎一样的思路，26题是只保留1个，此题是保留2个，已经在这里记录过题解。

由于是保留2个相同数字，对于前2个数字，我们可以直接保留。
对于后面的任意数字，能够保留的前提是：与当前写入的位置前面的第2个元素进行比较，不相同则保留。

将问题衍生至保留k个数字，则可以扩展为：

在有序数组的前k个元素里，每种数字都会符合不超过k个的条件；反向思考，一个数字与写入位置的第前k个元素对比，如果相同，证明写入位置之前已经写满了k个当前元素，那么写入位置就需要寻找一个新元素写入了，如果不同，就把当前元素复制过去补位。

所以，通用的Python实现代码如下：

def process(nums, k):
    # idx记录最初的写入位置，直接保留了前k位
    idx = k

    # 从第k位往后遍历，判断是否满足上面的第二条推定
    for x in nums[k:]:
        if nums[idx-k] != x:
            nums[idx] = x
            idx += 1
    return idx

时间复杂度O(n)
空间复杂度O(1)

那么这题的题解就可以写成：

# Python3实现

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        idx = 2

        for x in nums[2:]:
            if nums[idx-2] != x:
                nums[idx] = x
                idx += 1
        return idx

练习一下Rust

impl Solution {
    pub fn remove_duplicates(nums: &mut Vec<i32>) -> i32 {
        if nums.is_empty() {
            return 0;
        }

        if nums.len() <= 2 {
            return nums.len() as i32;
        }

        let mut i = 2;
        for j in 2..nums.len() {
            if nums[i-2] != nums[j] {
                nums[i] = nums[j];
                i += 1;
            }
        }
        i as i32
    }
}

总结

参考之前的题解，注意总结顺序遍历中“保留逻辑”的套路。