设备中存有 n 个文件，文件 id 记于数组 documents。若文件 id 相同，则定义为该文件存在副本。请返回任一存在副本的文件 id。

示例 1：

**输入：**documents = [2, 5, 3, 0, 5, 0]
**输出：**0 或 5

提示：

0 ≤ documents[i] ≤ n-1

2 <= n <= 100000

原地排序，由题目documents[i]的范围可得数组下标与元素是一一对应的，

所以遍历下标时只需要考虑当前值和下标是否相等

不相等要把元素交换到对应下标直到当前下标是对应的元素

或者当前元素对应下标所含元素已经是正确的值（此时交换会死循环，也即找到重复值）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    int findRepeatDocument(vector<int> &documents) {
        for (int i = 0; i < documents.size(); i++) {
            if (i == documents[i])
                continue;
            if (documents[i] == documents[documents[i]])
                return documents[i];
            int mid = documents[i];
            documents[i] = documents[documents[i]];
            documents[mid] = mid;
            i--; // 交换过来的元素需要重新判断
        }
        return -1;
    }
};