image.png
- 可以先排序,然后循环判断前后数字是否一样,最后得到重复的数字
- 也可以用桶排序的思想,进行如果有相同的就放进相同的桶,然后输出就行,不过需要O(n)的空间.
- 以下的方法是基于交换的排序,有点迷.原理不知道.
#include <iostream>
using namespace std;
int duplicate(int *nums,int length,int *duplication)
{
if(nums == nullptr || length<=0)
return 0;
for(int i=0;i<length;++i){
if(nums[i]<0||nums[i]>length-1)
return 0;
}
for(int i=0;i<length-1;i++){
while(nums[i]!=i){ // 注意这里循环结束的条件.
if(nums[i] == nums[nums[i]])
{
*duplication = nums[i];
return 1;
}
else{
int temp = nums[i];
nums[i] = nums[temp];
nums[temp] = temp;
}
}
}
}
int main() {
int duplication = -1;
int nums[]={1,3,2,2,3,5,3};
if(duplicate(nums,sizeof(nums)/sizeof(int),&duplication)){
cout << "the duplication is:" << duplication;
}
return 0;
}
