一亩三分地论坛

 找回密码
 获取更多干货,去instant注册!

扫码关注一亩三分地公众号
查看: 732|回复: 11
收起左侧

[Leetcode] LC 287 Find the Duplicate Number 二分查找的方法看不懂

[复制链接] |试试Instant~ |关注本帖
南方Giraffe 发表于 2016-8-15 22:35:29 | 显示全部楼层 |阅读模式

注册一亩三分地论坛,查看更多干货!

您需要 登录 才可以下载或查看,没有帐号?获取更多干货,去instant注册!

x
本帖最后由 南方Giraffe 于 2016-8-15 22:39 编辑

题目是:
https://leetcode.com/problems/find-the-duplicate-number/
public int findDuplicate(int[] nums) {            int low = 1, high = nums.length - 1;   
    while (low <= high) {        
        int mid = (int) (low + (high - low) * 0.5);        
        int cnt = 0;        
        for (int a : nums) {            
            if (a <= mid)
           ++cnt;        
        }        
        if (cnt <= mid)
            low = mid + 1;        
        else high = mid - 1;   
    }   
    return low;
}
这个答案看不懂,没有任何头绪,求指点


 楼主| 南方Giraffe 发表于 2016-8-15 22:36:47 | 显示全部楼层
抱歉,直接粘贴过来的答案没有排好版,这是答案的链接
https://discuss.leetcode.com/top ... using-binary-search
回复 支持 反对

使用道具 举报

twilightspark 发表于 2016-8-16 00:08:23 | 显示全部楼层
public int findDuplicate(int[] nums) {  
           int low = 1, high = nums.length - 1;   
    while (low < high) {    // this should be low < high, so when low = high, the index is the target we want.   
        int mid = (int) (low + (high - low) * 0.5);        
        int cnt = 0;        
        for (int a : nums) {            
            if (a <= mid) // count the number of elements not larger than mid.
           ++cnt;        
        }        
        if (cnt <= mid) // if the number no larger than mid, there are no duplicates for the number not larger than mid
        // since if there is, for the number larger than mid, there must also be a duplicated number(or else it cannot have enough element)
        // which breaks the rule for only one duplicated number.
            low = mid + 1;        
        else high = mid;   // for the opposite, since there must be a duplicate for the number no larger than mid, the number larger than mid shall be excluded.
        // it is impossible that the duplicated number is larger than n.
        // I think it is rather "high = mid" since the mid may also be the possible target.
    }   
    return low;
}

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

indpoor 发表于 2016-8-16 11:00:18 | 显示全部楼层
CNT代表的是小于等于mid的数的个数,如果cnt < mid表明重复的数不再[low, mid]之间, 自然 low = mid +1,剩下的分析类似。另外注意看题目,如果数组的长度是n,能选得数只能实在【1,n-1】之间,且重复的数只有一个,这道题的bs是基于这两个特定条件的。

评分

1

查看全部评分

回复 支持 反对

使用道具 举报

 楼主| 南方Giraffe 发表于 2016-8-17 15:53:07 | 显示全部楼层
indpoor 发表于 2016-8-16 11:00
CNT代表的是小于等于mid的数的个数,如果cnt < mid表明重复的数不再[low, mid]之间, 自然 low = mid +1,剩 ...

明白了,之前把low跟high错认为是index了,感谢
回复 支持 反对

使用道具 举报

susie_91 发表于 2016-9-14 14:58:04 | 显示全部楼层
LZLZ还在吗,我看你usc申了3个program,EE, DTIN, CSES,其中dtin和cses是???
回复 支持 反对

使用道具 举报

 楼主| 南方Giraffe 发表于 2016-9-14 21:35:49 | 显示全部楼层
susie_91 发表于 2016-9-14 14:58
LZLZ还在吗,我看你usc申了3个program,EE, DTIN, CSES,其中dtin和cses是???

前面那个好像叫data informatics,后面那个就是Computer Science (Engineer & Scientist),我们俗称的转专业37学分项目
回复 支持 反对

使用道具 举报

susie_91 发表于 2016-9-15 13:06:54 | 显示全部楼层
南方Giraffe 发表于 2016-9-14 21:35
前面那个好像叫data informatics,后面那个就是Computer Science (Engineer &amp; Scientist),我们俗称的转 ...

好哒 谢谢 di还收转专业的啊!很少报这个转专业的录取哎地里
回复 支持 反对

使用道具 举报

Eric_Wenyi 发表于 2016-10-6 06:47:40 | 显示全部楼层
楼主楼主,最后你饭大和CMU-SV spring选了哪一个呀
回复 支持 反对

使用道具 举报

 楼主| 南方Giraffe 发表于 2016-10-6 07:11:01 | 显示全部楼层
Eric_Wenyi 发表于 2016-10-6 06:47
楼主楼主,最后你饭大和CMU-SV spring选了哪一个呀

最后秋季去了NYU-Courant 然后准备转去SV
回复 支持 反对

使用道具 举报

Eric_Wenyi 发表于 2016-10-6 07:15:41 | 显示全部楼层
楼主你那时候大约是什么时候开始申请的呀。我现在因为还在等一封推荐信所以比较慌。
回复 支持 反对

使用道具 举报

 楼主| 南方Giraffe 发表于 2016-10-6 07:32:07 | 显示全部楼层
Eric_Wenyi 发表于 2016-10-6 07:15
楼主你那时候大约是什么时候开始申请的呀。我现在因为还在等一封推荐信所以比较慌。

11月底 字数字数
回复 支持 反对

使用道具 举报

本版积分规则

请点这里访问我们的新网站:一亩三分地Instant.

Instant搜索更强大,不扣积分,内容组织的更好更整洁!目前仍在beta版本,努力完善中!反馈请点这里

关闭

一亩三分地推荐上一条 /5 下一条

手机版|小黑屋|一亩三分地论坛声明 ( 沪ICP备11015994号 )

custom counter

GMT+8, 2016-12-4 05:52

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

快速回复 返回顶部 返回列表