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

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 lo; 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 };

 

转载于:https://www.cnblogs.com/love-yh/p/7103271.html

总结

以上是生活随笔为你收集整理的[Leetcode] Remove duplicates from sorted array ii 从已排序的数组中删除重复元素的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。