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

LeetCode-287 Find the Duplicate Number