Description
给定一个包含 \(n + 1\) 个整数的数组 \(nums\) ，其数字都在 \([1, n]\) 范围内（包括 \(1\) 和 \(n\)），可知至少存在一个重复的整数。
假设 \(nums\) 只有 一个重复的整数 ，返回 这个重复的数 。
你设计的解决方案必须 不修改 数组 \(nums\) 且只用常量级 \(O(1)\) 的额外空间。
Constraints
\(1 \le n \le 10^5\)
Solution
不考虑位置关系可以使用置换法。也就是说使得\(nums[i] == i\)，如果无法达成，那就是存在重复的数。这种方法满足时间复杂度\(O(n)\)，空间复杂度\(O(1)\)。但是落地到实现的话，需要考虑偏移量。
考虑位置关系的话推荐看这里的题解。其中一种解法是使用建图的方法，为每一个\(i\)建立\(i \to nums[i]\)的边，就可转换为判环入口问题。
题目的要求很高。但是参数给出的是vector&而不是const vector&，那就别怪我不客气了。
Code
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int *off = nums.data() - 1;
int n = nums.size() - 1;
for(int i = 1; i <= n; ++i) {
// Assert: off[i] > 0.
while(off[i] != off[off[i]]) {
swap(off[i], off[off[i]]);
}
if(off[i] != i) return off[i];
}
return off[n+1];
}
};