Givenasortedarray,removetheduplicatesinplacesuchthat>eachelementappearonlyonce
andreturnthenewlength.
Donotallocateextraspaceforanotherarray,youmustdothisinplacewithconstantmemory.
Forexample,GiveninputarrayA=[1,1,2],
Yourfunctionshouldreturnlength=2,andAisnow[1,2].
这道题目与前一题RemoveElement比较类似。但是在一个排序好的数组里面删除重复的元素。
首先我们需要知道，对于一个排好序的数组来说，A[N+1]>=A[N]，我们仍然使用两个游标i和j来处
理，假设现在i=j+1，如果A[i]==A[j]，那么我们递增i，直到A[i]!=A[j]，这时候我们再设置A[j+1]=
A[i]，同时递增i和j，重复上述过程直到遍历结束。
代码如下：
classSolution{
public:
intremoveDuplicates(intA[],intn){
if(n==0){
return0;
}
intj=0;
for(inti=1;i<n;i++){
if(A[j]!=A[i]){
A[++j]=A[i];
}
}
returnj+1;
}
};
譬如一个数组为1，1，2，3，首先i=1，j=0，这时候A[i]=A[j]，于是递增i，碰到2，不等于1，此时设置
A[j+1]=A[i]，也就是A[1]=A[2]，递增i和j为3和1，这时候A[3]!=A[1]，设置A[j+1]=A[i]，也就是A[2]=
A[3]，再次递增，遍历结束。这时候新的数组长度就为2+1，也就是3。
Followupfor"RemoveDuplicates":Whatifduplicatesareallowedatmosttwice?
Forexample,GivensortedarrayA=[1,1,1,2,2,3],
Yourfunctionshouldreturnlength=5,andAisnow[1,1,2,2,3].
紧接着上一题，同样是移除重复的元素，但是可以允许最多两次重复元素存在。
RemoveDuplicatesfromSortedArray
RemoveDuplicatesfromSortedArrayII
7RemoveDuplicatesfromSortedArray
评论0
最新资源