FindTheDuplicateNumber

FindTheDuplicateNumber

Description

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.

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.

Example

Example 1:

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

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

Analysis

在输入的数组 $arr[1,…,n+1]$ 中，其元素 $1 \le arr[i] \le n$。数组中所有元素只出现一次，但有一个元素例外，它出现了两次。现在需要找出这个重复出现的元素。

看完题目，立刻可以有两个想法：

$O(nlogn)$ 时间复杂度，$O(1)$ 空间复杂度

对数组进行排序，然后遍历一有序数组，查看下一个元素是否与当前元素相同。
$O(n)$ 时间复杂度，$O(n)$ 空间复杂度

使用 bool 访问数组进行标记，查找重复标记的元素。

但是，题目的要求是时间复杂度小于 $O(n^2)$，空间复杂度在常量 $O(1)$ 级别，而且不能对原数组进行修改。这三条限制，是这道题最大的挑战，而且前面两种算法均不满足。

Linked List Cycle Like

对于数组，我们把 $arr[1…n+1]$ 中的元素当作链表的节点，每一个元素 $arr[i]$ 是其指向的下一个节点的坐标。也就是说，$Node[i].next = arr[i], 1 \le i \le n + 1$。
我们取 $arr[0]$ 作为链表的入口。由于重复的只有一个数字，所以只要进入链表内，无论链表呈现何种链接状态，其中一个节点会被访问两次。
这个被访问两次的节点，就是我们要找的重复元素。
那么问题就变成了寻找一个在链表中查找回环的算法，且算法时间复杂度小于 $O(n^2)$，空间在常量 $O(1)$ 级别。
这个算法是很十分经典的，和数学中的追及问题一样。我们利用两个指针从链表入口开始遍历链表，一个步长为2的 fast 指针，一个步长为1的 slow 指针，也就是两个不同访问速度的指针。如果链表有回环，那么这两个指针一定会相遇。这时，我们令 fast 重新回到链表入口，让两个指针再次向前运动，但步长为1。这样，两个指针会再次相遇，相遇时的地方，就是回环入口，也就是我们要找的重复元素位置。
正确性证明如下：设从链表入口到回环入口的长度为 s，两个指针第一次相遇时，slow 走过的长度为 k，fast 走过的长度为 2k，环的长度为 r。那么，我们可以得到:
$$2k-k=k=nr, n \in 1,2…$$
$$s=k-m=nr-m=(n-1)r+(r-m)$$
如果我们取 $n=1$，那么我们可以得到，$s=r-m$。所以，我们让 fast 在第一次相遇后，从链表入口以步长为1开始前进，那么我们可以在回环入口处让 fast 和 slow 相遇，二者这次走过的距离都是 $r-m$。

算法的时间复杂度为 $O(2n) = O(n)$，空间复杂度为 $O(1)$，而且没有修改数组，是满足要求的。

AC Picture

Code

int findDuplicate(vector<int>& nums) {
    int fast = nums[nums[0]], slow = nums[0];
    while (fast != slow) {
        fast = nums[nums[fast]];
        slow = nums[slow];
    }
    fast = 0;
    while (fast != slow) {
        fast = nums[fast];
        slow = nums[slow];
    }
    return fast;
}