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];
    }
};

Link

LeetCode-287 Find the Duplicate Number