LeetCode 80—— 删除有序数组中的重复项 II

阅读目录

• • 1. 题目
  • 2. 解题思路
  • 3. 代码实现

    1. 题目

    

    2. 解题思路

    

    • 让 index指向删除重复元素后数组的新长度；
    • 让 st_idx 指向重复元素的起始位置，而 i 指向重复元素的结束位置，duplicate_num代表重复元素的个数；
    • 一段重复元素结束后，这时候如果 st_idx = index，那么无需搬移数据，只让 index 前进最多 2 个位置即可，如上面上图到右图的过程所示；
    • 如果 st_idx != index，我们需要从 st_idx 开始最多搬移 2 个数据到 index 位置，如上面右图到左图的过程所示；
    • 此时，如果 i 指向最后一个元素，那么直接将最后一个元素搬移到 index 位置，直接返回；
    • 如果 i 还没有到最后一个元素，那么继续重复寻找下一段重复元素；

      3. 代码实现

      class Solution:
          def removeDuplicates(self, nums: List[int]) -> int:
              if len(nums)  
      时间复杂度为  
           
            
             
             
               O 
              
             
               ( 
              
             
               n 
              
             
               ) 
              
             
            
              O(n) 
             
            
          O(n)，最多遍历 2 遍数组，空间复杂度为  
           
            
             
             
               O 
              
             
               ( 
              
             
               1 
              
             
               ) 
              
             
            
              O(1) 
             
            
          O(1)。
       
      当然了，上面的思路不容易理清，比较简单的一个实现是利用快慢指针。一开始快慢指针都指向第 3 个元素，如果 nums[fast] = nums[slow-2]，说明重复元素超过了 2 个，只需要向前移动 fast 指针即可；如果 nums[fast] != nums[slow-2]，那么把 fast 指针指向的元素移动到slow 指针，二者都前进一步。最后，slow指针指向的位置即为结果所求。
       
      class Solution {
      public:
          int removeDuplicates(vector& nums) {
              if (nums.size()