首页 > 代码库 > [Leetcode] Remove duplicates from sorted array ii 从已排序的数组中删除重复元素

[Leetcode] Remove duplicates from sorted array ii 从已排序的数组中删除重复元素

2024-10-15 08:32:39   213人阅读

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array A =[1,1,1,2,2,3],

Your function should return length =5, and A is now[1,1,2,2,3].

 题意：可以保留一个重复的元素。

思路：第一种是和Remove duplicates from sorted array类似的思想。隔一个比较一次，拿A =[1,1,1,2,2,3]举例子，其对比的过程如下

技术分享

技术分享 

技术分享

这里可以将第6行、第10行的2改为3，则至多重复的数字出现三次，代码为：

 1 class Solution 
 2 {
 3 public:
 4     int removeDuplicates(int A[], int n) 
 5     {
 6         if(n<=2)    return n;
 7         int lo=2;
 8         for(int i=2;i<n;++i)
 9         {
10             if(A[i] !=A[lo-2])
11                 A[lo++]=A[i];
12         }
13         return index;
14     }
15 };

方法二：使用计数器，当两者不相等计数器重置，将A[i]赋值给A[lo]的下一位；相等时但是count不超过2，将A[i]赋值给A[lo]的下一位，其余，仅计数器++，这样就可以成功将不等的情况后的，出现第二个和A[i]相等的情况时，将其也赋值给前面的元素。

 1 class Solution {
 2 public:
 3     int removeDuplicates(int A[], int n) 
 4     {
 5         int lo=0;
 6         int count=0;
 7         if(n<3) return n;
 8 
 9         for(int i=1;i<n;i++)
10         {
11             if(A[lo]==A[i])
12             {
13                 count++;
14                 if(count<2)
15                     A[++lo]=A[i];
16             }
17             else
18             {
19                 A[++lo]=A[i];
20                 count=0;
21             }
22         }
23         return lo+1;
24     }
25 };

 

[Leetcode] Remove duplicates from sorted array ii 从已排序的数组中删除重复元素


联系
我们