问题抽象

数组中有未知个数、未知次数的重复数，随意找出一个即可

算法：哈希，标记法

难点在于想到空间复杂度为$O(N)$的标记解法，并且将其转换为在原数组上标记的解法

关键点是意识到数组的值范围在[0,n-1],可以在原数组上做标记，标记后的数应该落在[0,n-1]之外，因此不能直接取负，要加上一个偏移量。

复杂度

时间：$O(N)$
空间：$O(1)$

代码

class Solution {
public:
    int findRepeatNumber(vector<int>& nums) {
        int ans;
        for(auto x : nums){
            if(x < 0) x = -(x+1);
            if(nums[x] < 0){
                ans = x;
                break;
            }
            nums[x] = -(nums[x]+1);
        }

        return ans;
    }
};