《leetCode》：Remove Duplicates from Sorted Array II

本文主要是介绍《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 nums = [1,1,1,2,2,3],Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

题目大意：将一个已排序的数组中元素出现的次数大于2次的元素的多余部分去除掉。

思路：借助了一个额外数组temp来进行拷贝，最后将temp中的元素全部拷贝回去。


#include<stdio.h>
#include<stdlib.h>
#include<string.h>
int removeDuplicates(int* nums, int numsSize) {if(nums==NULL||numsSize<1){return 0;}if(numsSize<=2){return numsSize;}//开辟一段空间来进行存储int *temp=(int *)malloc(numsSize*sizeof(int));if(temp==NULL){exit(EXIT_FAILURE);}int index1=0;int index2=0;int count=1;int val; for(int i=1;i<numsSize;i++){if(nums[i]==nums[index1]){count++;}else{//nums[i]与nums[index]不相等,则将前面的数拷贝到temp数组中进行存储val=count;if(count>2){val=2;}for(int j=0;j<val;j++){temp[index2]=nums[index1+j];index2++;}index1=i;//将index1进行更新count=1;//将count进行还原，为下一步判断做准备}}//上面没有对最后的进行拷贝if(index1<numsSize){val=count;if(count>2){val=2;}for(int j=0;j<val;j++){temp[index2]=nums[index1+j];index2++;}}//再将temp中的数拷贝回去for(int i=0;i<index2;i++){printf("%d   ",temp[i]);nums[i]=temp[i];}return index2;
}int main(void){int k;while(scanf("%d",&k)!=EOF&&k>0){int *arr=(int *)malloc(k*sizeof(int));if(arr==NULL){exit(EXIT_FAILURE);}for(int i=0;i<k;i++){scanf("%d",arr+i);}printf("%d\n",removeDuplicates(arr,k));}
}

AC结果如下：

从AC结果可以看出，虽然AC了，但是，效率不高。仍需要改善。

每次AC完自己的代码之后，然后看别人的代码，发现自己真的好渣，虽然最后结果是AC了，但是代码质量没有别人的高

此博客（http://blog.sina.com.cn/s/blog_60b5450101017p33.html）提供了这样一种解法

/*
思路：先把序列的前两位放进去，然后让后面的和已经放进去的最后两位比较，如果相同，那么扔掉，如果不同，就放进去。
*/int removeDuplicates(int* nums, int numsSize) {if(nums==NULL||numsSize<1){return 0;}if(numsSize<=2){return numsSize;}int index=2;//始终指向即将要覆盖的位置for(int i=2;i<numsSize;i++){if(nums[i]!=nums[index-1]||nums[i]!=nums[index-2]){//跟已经放进去的后两个元素比较，看是否相同nums[index]=nums[i];index++;}}return index;}