题解 | 数组中重复的数字

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param numbers int整型vector 
     * @return int整型
     */
    int duplicate(vector<int>& numbers) {
        // write code here
        //1.hash表
        // if(numbers.size()>10000||numbers.size()<=0){
        //     return -1;
        // }
        // unordered_map<int,int> MyMap;
        // for(auto num : numbers){
        //     MyMap[num]++;
        //     if(MyMap[num]>=2){
        //         return num;
        //     }
        // }
        // return -1;

        //2.每次子循环保证一部分元素的键==值
        //官方题解：https://blog.nowcoder.net/n/785481bddaf848b2bc138af3298aa236
        for(int i = 0; i < numbers.size(); i++){
            //该位置本来就是对的
            if(numbers[i] == i)
                continue;
            //位置不对，需要换到自己对应的位置
            else{
                //对应位置相等，重复
                if(numbers[i] == numbers[numbers[i]])
                    return numbers[i];
                //交换位置
                else{
                    swap(numbers[i], numbers[numbers[i]]);
                  	i--;
                }
            }
        }
        //没有重复
        return -1;
    }
};