首页 > 代码库 > [LeetCode] Remove Duplicates from Sorted Array II [27]
[LeetCode] Remove Duplicates from Sorted Array II [27]
题目
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]
.
原题链接(点我)
解题思路
移除数组中重复次数超过2次以上出现的数,但是可以允许重复2次。
这个题类似Remove Duplicates from Sorted Array,第一个想法很直接就是计数,超过2次的就忽略,依据这个思路的代码见代码一;
上面的思路可行,但是代码看着比较冗余,判断比较多。再来想想原来的数组,该数组是排好序的,如果一个数出现3次以上,那么必有A[i] == A[i-2]。所以根据这个关系可以写出比较精简的代码二。详见代码。
代码实现
代码一
class Solution { public: int removeDuplicates(int A[], int n) { if(A==NULL || n<=0) return 0; int start=1, count = 1, back = A[0]; for(int i=1; i<n; ++i){ if(count<2){ A[start++] = A[i]; if(back != A[i]){ back = A[i]; count = 1; }else{ ++count; } }else{ if(A[i] != back){ count = 1; A[start++] = A[i]; back = A[i]; }else{ ++count; } } } return start; } };
代码二
class Solution { public: int removeDuplicates(int A[], int n) { if(A==NULL || n<=0) return 0; if(n==1) return 1; int start=1,back = A[1]; for(int i=2; i<n; ++i){ if(A[i] != A[i-2]){ A[start++] = back; back = A[i]; } } A[start++] = back; return start; } };
如果你觉得本篇对你有收获,请帮顶。
另外,我开通了微信公众号--分享技术之美,我会不定期的分享一些我学习的东西.
另外,我开通了微信公众号--分享技术之美,我会不定期的分享一些我学习的东西.
你可以搜索公众号:swalge 或者扫描下方二维码关注我
(转载文章请注明出处: http://blog.csdn.net/swagle/article/details/29822565 )
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。