找出数组中重复元素

题目描述

一个大小为n的数组，里面的数都属于范围[0, n-1]，有不确定的重复元素，找到至少一个重复元素；
要求O(1)空间和O(n)时间；

方法1

因为数组长度为n，且数的范围为[0~n-1]，且包含重复元素，故将数组中的每个元素置位到和坐标值相同的位置，0->0,1->1,2->2，以此类推，如果存在重复元素，则必然会使某两个位置上的元素值相同。

int find_rongyu(vector<int> res){
    if (res.size() <= 1)return 0;
    for (int i = 0; i < res.size(); i++){
        while (i != res[i]){
            if (res[i] == res[res[i]])return res[i];
            swap(res[i], res[res[i]]);
        }
    }
    return 0;
}

方法2

对以数组元素值为下标的数组元素值加上n。
将数组中的某个元素值res[i]作为下标，若res[res[i]] >= n时，则判断已经进行过加法运算，此下标为重复元素值。否则，对res[res[i]]+=n处理；

int find_rongyu1(vector<int> res){
    if (res.size() <= 1)return 0;
    int n = res.size();
    for (int i = 0; i < n; i++){
        if (res[i] >= n){
            return i;
        }
        res[res[i]] += n;
    }
    return 0;
}

方法3

可以将此问题看作是一个“判断单链表是否存在环，若存在找出环”的问题。
单链表采用数组实现，每个元素值作为next指针，指向下一个元素，可以将问题转化为“已知一个单链表存在环，找出环的入口点”。
思路：将res[i]看做是第 i 个元素的索引，即res[i] -> res[res[i]]-> res[res[res[i]]]…最终形成一个单链表，由于数组存在重复元素，则一定存在一个环，且环的入口点就是重复元素。

int find_rongyu2(vector<int> res){
    if (res.size() <= 1)return 0;
    int x, y;
    x = y = 0;
    do{
        x = res[res[x]];
        y = res[y];
    } while (x != y);
    x = 0;
    do{
        x = res[x];
        y = res[y];
    } while (x != y);
    return x;
}