题目描述

给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。

样例

输入: [1,3,4,2,2]
输出: 2

输入: [3,1,3,4,2]
输出: 3

算法1

(二分) $O(nlogn)$

在1~n中二分找答案，假设现在取的数为mid，遍历一下数组，看小于等于mid的数是不是有mid个，如果多了，说明1~mid中有重复，否则mid~n中有重复。

时间复杂度

二分O(logn),每一次需要遍历数组，故O(nlogn)。

参考文献

C++ 代码

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        if (nums.empty()) return 0;
        int n = nums.size() - 1, l = 1, r = n;
        while (l <= r){
            int mid = l + (r - l) / 2;
            int cnt = 0;
            for (int i = 0; i < n + 1; ++i){
                if (nums[i] <= mid) ++cnt;
            }

            if (cnt > mid) r = mid - 1;
            else l = mid + 1;
        }

        return l;
    }
};

算法2

(快慢指针) $O(n)$

设当前下标为idx，令idx指向nums[idx]，问题可以转化为带环链表求环入口。

时间复杂度

参考文献

C++ 代码

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        if (nums.empty()) return 0;
        int slow = nums[0], fast = nums[0];
        while (true){
            slow = nums[slow];
            fast = nums[nums[fast]];
            if (slow == fast) break;
        }

        slow = nums[0];
        while (slow != fast){
            slow = nums[slow];
            fast = nums[fast];
        }

        return fast;
    }
};