算法|题解

LeetCode 287 Find the Duplicate Number

凝神长老 · 2月22日 · 2019年 · 1644次已读

本文写于 2019年02月22日,距今已超过 1 年,距 2020年03月27日 的最后一次修改也已超过 3 个月,部分内容可能已经过时,您可以按需阅读。如果图片无法显示或者下载链接失效,请给我反馈,谢谢!


4 1 投票
评分

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;
}
4 1 投票
评分
4 1 投票
评分
订阅评论动态
提醒
guest
3 评论
最新
最旧 得票最多
行内反馈
查看所有评论
Hi
Hi Chrome 74.0.3729.108 Mac OS X 10_13_6
2019年6月19日 03:09

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

666
666 Chrome 85.0.4183.83 Windows 10
2020年10月21日 11:58
我对这篇文章的评分 :
     

666