287.Find the Duplicate Number¶

287.Find the Duplicate Number¶

Tags: Medium Two Pointers Binary Search

Links: https://leetcode.com/problems/find-the-duplicate-number/

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Example 1:

Input: [1,3,4,2,2]
Output: 2

Example 2:

Input: [3,1,3,4,2]
Output: 3

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(*n*2).
There is only one duplicate number in the array, but it could be repeated more than once.

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = nums.size();
        int left = 1, right = n - 1;
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            int cnt = 0;
            for (int i = 0; i < n; ++i) {
                if (nums[i] <= mid) ++cnt;
            }
            if (cnt <= mid) left = mid + 1;
            else right = mid;
        }

        return left;
    }
};

二分法，因为结果肯定在1-n之间，所以可以先猜测结果，然后二分查找答案，类似于《挑战程序设计竞赛》里的先猜测答案。

$O(n)$ 的解法，快慢指针的思路。这种方法是由Floyd提出的，参考之前链表的题目。

将数组的下标和数组元素组成一个二元组，即(index, num[index])，进而让下一个二元组为(num[index], num[num[index]])，于是有一个映射函数f，新的下标 $x_{i+1}=f(x_i)$ ，于是可以得到一系列二元组，如果没有重复的元素，这个二元组可以一直写下去不重复，但是元素的数据范围是1-n，那么就一定会存在环。

这里借鉴一下一个对于序列的环的类型的分析，主要是线性型，P型和首尾相连的O型。

假设函数f从定义域映射到它本身，此时会有3种情况。首先，如果定义域是无穷的，则序列是无限长并且没有循环的。例如，函数 f(n) = n + 1，在整数范围内满足这个性质 - 没有数字是重复的。 第二， 序列可能是一个闭合循环，这意味着存在一个i使得x_0 = x_i。在这个例子中，序列在一组值内无限循环。第三，序列有可能是的“ρ型的”，此时序列看起来像下面这样：

      x_0 -> x_1 -> ... x_k -> x_{k+1} ... -> x_{k+j}
                         ^                       |
                         |                       |
                         +-----------------------+

如果我们从下标0开始进行运算，那么永远不会有元素的值等于0，并且已经证明了存在环，那么必然是P型，并且可以得到重复元素一定是环的入口点。于是问题来到了如何找到环的入口点。（这里最好不要去写出数组画环，因为很容易乱掉，不如就写出表达式理论推导，会更清晰）

快慢指针里快指针速度是慢指针的2倍，于是

设从头节点到环的起点距离为 $a$ ，环的起点到第一次相遇的节点之间的距离为 $b$ ，第一次相遇节点到尾端距离为 $c$ ，显然 $b+c$ 为环一圈的周长。

那么存在如下等式关系： $$ t = a + b \ 2t = a + b + k(b + c) \quad k \geq 1 \ \therefore a = (k - 1)(b + c) + c $$ 于是可以得出结论，当快慢指针相遇的时候，一个指针从起点出发，另一个指针从相遇点继续走，速度都和慢指针一样，那么起点出发的走过了距离a，意味着另一个指针绕了环k-1圈又走了c，于是相遇，据此就可以写出算法。

class Solution {
public:
    int findDuplicate(vector<int>& nums) {
        std::ios_base::sync_with_stdio(false);
        cin.tie(NULL);
        cout.tie(NULL);

        int n = nums.size();
        int slow = nums[0], fast = nums[nums[0]];
        while (fast != slow) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }

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

        return slow;
    }
};