关于leetcode:LeetCodeGolang-80-删除有序数组中的重复项-II

41次阅读

共计 795 个字符,预计需要花费 2 分钟才能阅读完成。

题目:

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

不要应用额定的数组空间,你必须在 原地 批改输出数组 并在应用 O(1) 额定空间的条件下实现。

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

题解:

首先,这是一道数组类的简略算法题。咱们明确循环不变式(loop invariant)的概念,即一组在循环体内、每次迭代均放弃为真的性质。

先贴代码:(GO 语言)

func removeDuplicates(nums []int) int {n := len(nums)
   if n < 3 {return n}
   slow, fast := 2, 2
   for fast < n {if nums[slow-2] != nums[fast] {nums[slow] = nums[fast]
         slow++
      }
      fast++
   }
   return slow
}

咱们设置的循环不变式:slow指针之前的数组元素(不蕴含目前所指元素)最多有两个反复。同时应用快慢指针的形式。

  • 初始 slow 设为 2,即nums[2] 之前的元素不反复,因为 nums[2] 之前最多有两个元素,肯定不会呈现两个以上的反复,所以 slow 地位满足不变式要求。
  • 接下来的循环中,如果 nums[fast]nums[slow-2]不雷同,则将 nums[fast] 赋值给 nums[slow] 后后移 slow,完结本次循环。如果nums[fast]nums[slow-2]雷同,则间接完结本次循环。每次循环,slow地位均满足不变式要求。
  • 最终 fast 指针遍历完数组元素后,完结整个循环,slow地位满足不变式要求。

因而在循环完结后,slow左侧元素最多只有两个反复元素,合乎算法要求。

复杂度剖析:

  • 工夫复杂度:O(n),其中 n 是数组的长度。咱们最多遍历该数组一次。
  • 空间复杂度:O(1),咱们只须要常数的空间存储若干变量。

正文完
 0