描述

Given a sorted array, remove the duplicates in place such that each element appear only once

and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example, Given input array A = [1,1,2],

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


要求时间复杂度为O（n）,空间复杂度为O（1）

#include<iostream>#include<assert.h>#include<vector>#include<algorithm>usingnamespacestd;classSolution{public:intremoveDuplicates(char*a,size_tlen){assert(a);size_tindex=1;intfirst=0;intsecond=1;while(second<len){if(a[second]!=a[first]){a[index++]=a[second];first=second;}second++;}returnindex;}};

以上是我自己看完题目后所编写的程序

分析：

len是数组元素的个数

first为第一个元素下标，second为第二个元素下标（如果数组只有一个元素，则不会进入循环，而是直接返回1）

index为复制后数组的个数


运行结果：

测试数组为char a[16] = { 1, 1, 1, 2, 2, 2,2,5 ,6,6,6,6,7,7,8,9};


以下是参考LeetCode中使用STL实现的代码

代码1：

classSolution{public:intremoveDuplicates(chara[],size_tlen){returndistance(a,unique(a,a+len));}};

所使用的函数：

template<classForwardIterator>ForwardIteratorunique(ForwardIteratorfirst,ForwardIteratorlast);

distance(InputIteratorfirst,InputIteratorlast);


代码2：

classSolution{public:intremoveDuplicates(chara[],size_tlen){return_removeDuplicates(a,a+len,a)-a;}template<classT1,classT2>T2_removeDuplicates(T1first,T1last,T2output){while(first!=last){*output++=first;first=upper_bound(first,last,*first);}returnoutput;}};

所使用的函数：

template<classForwardIterator,classT>ForwardIteratorupper_bound(ForwardIteratorfirst,ForwardIteratorlast,constT&value);

================================================================


描述

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]


要求时间复杂度为O（n）,空间复杂度为O（1）

classSolution2{public:intremoveDuplicates(inta[],size_tlen){return_removeDuplicates(a,a+len,a)-a;}template<classT1,classT2>T2_removeDuplicates(T1first,T1last,T2output){T1tmp=first;while(first!=last){if((tmp!=first-1)&&(*tmp==*(first-1))){*output++=*(first-1);}*output++=*first;tmp=first;first=upper_bound(first,last,*first);}returnoutput;}};

以上代码是我自己根据上题中使用STL进行部分代码修改实现成功的程序


运行结果：

测试数组为 int a[16] = { 1, 1, 1, 2, 2, 2,2,5 ,6,6,6,6,7,7,8,9};


以下是参考LeetCode中实现的代码

代码1：

classSolution2{public:intremoveDuplicates(int*a,size_tlen){size_tindex=2;for(inti=2;i<len;++i){if(a[i]!=a[index-2])a[index++]=a[i];}returnindex;}};

代码2：

classSolution2{public:intremoveDuplicates(int*a,size_tlen){intindex=0;for(inti=0;i<len;++i){if(i>0&&i<len-1&&a[i]==a[i-1]&&a[i]==a[i+1])continue;a[index++]=a[i];}returnindex;}};