C++ 中从已排序数组中删除重复项

假设我们有一个已排序数组 nums，我们需要就地删除其中的重复项，使得重复元素最多出现两次，并返回新的长度。为此，我们不能使用额外的空间。我们必须使用 O(1) 的空间量来解决此问题。例如，如果数组像 [0,0,0,1,1,1,1,2,3,3]，那么输出将为 [0,0,1,1,2,3,3]，长度为 7

让我们看看步骤 -

• len := 2 和 n := 数组大小
• 如果 n <= 2，则返回 n
• 对于 i := 2 至 n
  • 如果 nums[i] != nums[len - 2] 或 nums[i] != nums[len - 1]
    • nums[len] := nums[i]，并将 len 加 1
• 返回 len

为了更好地理解，让我们看看以下实现 -

示例

 演示

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   int removeDuplicates(vector<int>& nums) {
      int len = 2;
      int n = nums.size();
      if(n <= 2)return n;
      for(int i = 2; i < n; i++){
         if( nums[i] != nums[len - 2] || nums[i] != nums[len - 1]){
            nums[len] = nums[i];
            len++;
         }
      }
      return len;
   }
};
main(){
   Solution ob;
   vector<int> v = {0,0,0,1,1,1,1,2,3,3};
   cout << ob.removeDuplicates(v);
}

输入

[0,0,0,1,1,1,1,2,3,3]

输出

7

阿纳布·查克拉博蒂

更新于:2020-05-04

1 千次 + 浏览

开启你的职业

通过完成课程获得认证

开始