算法|题解

LeetCode 287 Find the Duplicate Number

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

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 条评论
说点什么

avatar

您可以根据需要插入表情、图片、音频、视频或者其他附件,也可以 @ 你需要提及的用户

  
不开心么么什么再见加油发火可以可怜可爱吐吐血吓呵呵哈哈哦哭哼喜欢嗯嘿嘿困圣诞坏笑圣诞调皮坏笑女汉子奸笑好的委屈宝宝害羞小清新心塞快哭了恭喜发财惆怅我最美抓狂抠鼻放空无奈晕汗泪奔温柔女生狗年生气笑笑泪衰调皮调皮女生鄙视酷静静额鼓掌
上传图片
 
 
 
上传视频和音频
 
 
 
上传其他类型文件
 
 
 
1 评论主题数
1 评论回复数
0 评论跟进人数
 
最近回复的评论
最热烈的讨论
2 评论人数
jxtxzzwHi 最近评论者

  订阅评论动态  
最新 最旧 得票最多
提醒
    Hi
    Hi
    离线
    9 月 之前 [2019-6-19 · 3:09]
    Chrome 74.0.3729.108 Mac OS X 10_13_6

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