算法

LeetCode 287 Find the Duplicate Number

jxtxzzw · 2月22日 · 2019年 · 756次已读

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.

这道题在没有限制的情况下做法有很多种,例如排序,然后找到 a[i] == a[i + 1]的,或者,桶排序,记录一下每个数出现了几次。

但是题目增加了很多限制条件

  • 不能更改原数组(假设数组是只读的)
  • 只能使用额外的 $O(1)$ 的空间
  • 时间复杂度小于 $O(n^2)$
  • 数组中只有一个重复的数字,但它可能不止重复出现一次

一开始想似乎是没有思路,但是如果把题目稍作变换,马上就可以变成很熟悉的题型。

数组长度是 n + 1,这意味着数组下标是 0 ~ n,同时,数组中的数的范围是 1 ~ n,因此,数组中元素的值的取值范围是数组下标取值范围的子集。

那么,如果把数组想象成一个不存放内容、只有指针的链表,数组元素的值是当前下标的后一个链表结点下标。举例来说,a[1] = 3,那么可以认为,标号为 1 的结点的 next 是编号为 3 的结点,即 node1 -> next = node3,类似地,如果 a[2] = 4, a[4] = 5,那么这个链表就是 node2 -> node4 -> node5。

这样一来,问题就换成了,给定一个链表,链表中有一个环,问,环的起点在哪?

典型的双指针问题。

至于,为什么链表一定有环,这是由题意显然的,那么,为什么所求的答案就是环与直线的交点?

简单说,就是:快指针走过 a + b + c + b,慢指针走过 a + b,又 2(a + b) = a + b + c + b,所以c = a。

详细的证明可以参考:https://blog.csdn.net/u013077144/article/details/81070415,以及https://blog.csdn.net/monkeyduck/article/details/50439840

代码如下:

class Solution {
    public int findDuplicate(int[] nums) {
        int slow = nums[0];
        int fast = nums[nums[0]];
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[nums[fast]];
        }
        fast = 0;
        while (slow != fast) {
            slow = nums[slow];
            fast = nums[fast];
        }
        return slow;
    }
}

这里的

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

就相当于链表写法中的

while (fast->next != nullptr && fast->next->next != nullptr) {
    fast = fast->next->next;
    slow = slow->next;
    if (fast == slow) break;
}
2 条回应
    Hi 2019-6-19 · 3:09
    Chrome 74.0.3729.108 Mac OS X 10_13_6

    为什么”链表一定有环,这是由题意显然的”?

      jxtxzzw 2019-6-19 · 10:45
      Chrome 75.0.3770.100 Windows 10

      要将 1 ~ n 填入 n + 1 长度的数组,由鸽笼原理,必存在至少出现 2 次的数(若每个数最多出现一次,则只能填满长度为 n 的数组)。根据上文的描述,将数组各位置的元素值看作链表的 next 指针指向的位置,那么,那个至少出现了 2 次的数,就会有多个入口(即多个数指向他),于是环存在。