跳至主要內容

0080. 删除有序数组中的重复项 II

ITCharge大约 2 分钟

0080. 删除有序数组中的重复项 IIopen in new window

  • 标签:数组、双指针
  • 难度:中等

题目大意

描述:给定一个有序数组 numsnums

要求:在原数组空间基础上删除重复出现 22 次以上的元素,并返回删除后数组的新长度。

说明

  • 1nums.length31041 \le nums.length \le 3 * 10^4
  • 104nums[i]104-10^4 \le nums[i] \le 10^4
  • numsnums 已按升序排列。

示例

  • 示例 1:
输入:nums = [1,1,1,2,2,3]
输出:5, nums = [1,1,2,2,3]
解释:函数应返回新长度 length = 5, 并且原数组的前五个元素被修改为 1, 1, 2, 2, 3 。 不需要考虑数组中超出新长度后面的元素。
  • 示例 2:
输入: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 。 不需要考虑数组中超出新长度后面的元素。

解题思路

思路 1:快慢指针

因为数组是有序的,所以重复元素必定是连续的。可以使用快慢指针来解决。具体做法如下:

  1. 使用两个指针 slowslowfastfastslowslow 指针指向即将放置元素的位置,fastfast 指针指向当前待处理元素。
  2. 本题要求相同元素最多出现 22 次,并且 slow2slow - 2 是上上次放置了元素的位置。则应该检查 nums[slow2]nums[slow - 2] 和当前待处理元素 nums[fast]nums[fast] 是否相同。
    1. 如果 nums[slow2]==nums[fast]nums[slow - 2] == nums[fast] 时,此时必有 nums[slow2]==nums[slow1]==nums[fast]nums[slow - 2] == nums[slow - 1] == nums[fast],则当前 nums[fast]nums[fast] 不保留,直接向右移动快指针 fastfast
    2. 如果 nums[slow2]nums[fast]nums[slow - 2] \ne nums[fast] 时,则保留 nums[fast]nums[fast]。将 nums[fast]nums[fast] 赋值给 nums[slow]nums[slow] ,同时将 slowslow 右移。然后再向右移动快指针 fastfast
  3. 这样 slowslow 指针左边均为处理好的数组元素,而从 slowslow 指针指向的位置开始, fastfast 指针左边都为舍弃的重复元素。
  4. 遍历结束之后,此时 slowslow 就是新数组的长度。

思路 1:代码

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        size = len(nums)
        if size <= 2:
            return size
        slow, fast = 2, 2
        while (fast < size):
            if nums[slow - 2] != nums[fast]:
                nums[slow] = nums[fast]
                slow += 1
            fast += 1
        return slow

思路 1:复杂度分析

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