数组中找重复数字1

image.png

1. 可以先排序,然后循环判断前后数字是否一样,最后得到重复的数字

2. 也可以用桶排序的思想,进行如果有相同的就放进相同的桶,然后输出就行,不过需要O(n)的空间.
3. 以下的方法是基于交换的排序,有点迷.原理不知道.

#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;
}