题目描述

给定一个长度为 n 的整数数组 nums，数组中所有的数字都在 0∼n−1 的范围内。

数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

注意：如果某些数字不在 0∼n−1 的范围内，或数组中不包含重复数字，则返回 -1；

样例

给定 nums = [2, 3, 5, 4, 3, 2, 6, 7]。

返回 2 或 3。

算法1

(模拟)

1. 这道题也可以用排序，但是排序的时度是$O(nlogn)$。
2. 采用 模拟交换的算法

   • while()循环可以保证跳出while()的时候，只有2种可能，第一种是位置1上的数字是1，这样不能说明数组有重复元素，但是如果是第2种，A[1] = A[5]，如果i != A[i]，就一定说明有重复元素。

3. 一开始需要对边界情况进行判断，如果有不在范围的，输出-1
4. 最后for()循环结束的时候，说明整个数组中没有重复的元素，输出-1。
5. for()循环种的第2个if可以只写i != A[i]，就可以AC，是可以理解的。但是不能只写一个A[i] == A[A[i]]，还没太想明白。知道的大佬可以告诉我一下hh。
6. 这道题本来想用排序，其实不用，因为while()走完后，完美的情况就排好序了，试验过了。

时间复杂度

$O(n)$

C++ 代码

class Solution {
public:
    int duplicateInArray(vector<int>& A) {
        int n = A.size();

        for(auto x : A)
            if(x < 0 || x >= n)
                return -1;

        for(int i = 0; i < n; i ++)
        {
            while(i != A[i] && A[A[i]] != A[i]) swap(A[i], A[A[i]]);
            if(i != A[i] && A[i] == A[A[i]]) return A[i];
        }

        return -1;
    }
};