明显如果你用一个辅助数组,复制下来,然后按照上面的方法来算的话,完全没有问题的.
2.另外的话,下面的方法是用二分计算的方法来算的,参考剑指offer.
#include <iostream>
using namespace std;
int countRange(const int*nums,int length,int start,int end);
int getDuplication(const int *nums,int length)
{
if(nums == nullptr||length <= 0){
return -1;
}
int start = 1;
int end = length-1;
while(end>=start){
int middle =((end-start)/2)+start;
int count = countRange(nums,length,start,middle);
if(end == start){
if(count >1)
return start;
else break;
}
if(count>(middle-start+1))
end = middle;
else
start = middle+1;
}
return -1;
}
int countRange(const int*nums,int length,int start,int end)
{
if(nums == nullptr)
return 0;
int count = 0;
for(int i =0;i<length;i++)
if(nums[i]>=start&&nums[i]<=end)
++count;
return count;
}
int main() {
int nums[]={0,1,2,4,3,3};
cout<<"the duplication is:"<< getDuplication(nums,sizeof(nums)/sizeof(int))<< "\n";
return 0;
}
