一亩三分地

 找回密码 注册账号

扫描二维码登录本站

BBS
指尖新闻
Offer多多
Salarytics
Learn
Who's Hiring?
疫情动态
Instant
客户端
微信公众号
扫码关注公众号
留学申请公众号
扫码关注留学申请公众号
Youtube频道
留学博客
关于我们
查看: 9510|回复: 41
收起左侧

[高频题] 【面试新题】绝妙的二分查找题,一定要练习一下

    [复制链接] |试试Instant~ |刷题, 二分/排序/搜索
我的人缘0

分享帖子到朋友圈
tinlittle | 显示全部楼层 |阅读模式
本楼: 👍   100% (19)
 
 
0% (0)   👎
全局: 👍   98% (3019)
 
 
1% (57)    👎

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

您需要 登录 才可以下载或查看,没有帐号?注册账号

x
刚看到一道二分查找面试真题,题型和所用的模版和已有的二分题模版都不同,有那么一点quick select的意思又有些不同。鉴于二分查找本是面试官最爱问的题,但原题数目有限,时间久了,人人都做熟了,就不再问了。若市面上出个新马甲,可能会被问一段时间。建议刚写过十来道二分原题的新手试试这道题。
游客,本帖隐藏的内容需要积分高于 200 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.

评分

参与人数 45大米 +148 收起 理由
lemoncorn1123 + 1 很有用的信息!
jesse1204 + 2 很有用的信息!
doubleyanng + 1 给你点个赞!
tony.hu1213 + 2 很有用的信息!
notavailable + 2 给你点个赞!
lq24 + 1 赞一个
shikezhang + 1 谢谢楼主,已加米!
wz30 + 1 赞一个
GhostZ + 3 很有用的信息!
JoyForce + 2 给你点个赞!

查看全部评分


上一篇:问一道题的follow up
下一篇:Coding Interview University

本帖被以下淘专辑推荐:

我的人缘0
 楼主| tinlittle 2019-5-16 13:28:14 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (3019)
 
 
1% (57)    👎
加一个简短的,大家更熟悉的非递归实现:
游客,本帖隐藏的内容需要积分高于 200 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.

评分

参与人数 1大米 +30 收起 理由
admin + 30

查看全部评分

回复

使用道具 举报

我的人缘0
Tina_Qity 2019-5-17 12:41:34 | 显示全部楼层
本楼: 👍   100% (5)
 
 
0% (0)   👎
全局: 👍   100% (47)
 
 
0% (0)    👎
发个java的,请指点
[Java] 纯文本查看 复制代码
public int findKthMissing(int[] nums, int k) {
        if (nums == null || nums.length < 2) {
        	return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left + 1 < right) {
        	int mid = left + (right - left) / 2;
        	int all = (nums[mid] - nums[left] + 1) - (mid - left + 1);
        	if (k > all) {
        		k -= all;
        		left = mid;
        	} else {
        		right = mid;
        	}
        }
        if (nums[left] + k >= nums[right]) {
        	return -1;
        } else {
        	return nums[left] + k;
        }
    }


补充内容 (2019-5-17 12:42):
不太会用加代码== 所以就成这个版面了==

补充内容 (2019-5-17 12:43):
又显示出来啦 尴尬

评分

参与人数 11大米 +68 收起 理由
gretyy + 2 给你点个赞!
wangbd + 1 给你点个赞!
BirkhoffG + 4 给你点个赞!
tl2k3 + 1 赞一个
gumo0515 + 1 赞一个
simple_xp + 2 666
coloor + 1 赞一个
kyzgz + 2 给你点个赞!
詹姆斯魏 + 1 赞一个
admin + 50

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| tinlittle 2019-5-17 13:00:48 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (3019)
 
 
1% (57)    👎
回应地里新农,重贴降低隐藏积分限制。
游客,本帖隐藏的内容需要积分高于 120 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
回复

使用道具 举报

我的人缘0
admin 2019-5-18 03:45:11 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   93% (2561)
 
 
6% (189)    👎
本文被选为全站置顶文章之一。
作者获得大米奖励。谢谢你的分享。

贴代码的同学,都获得了大米奖励。
回复

使用道具 举报

我的人缘0
pandami 2019-5-18 06:23:12 | 显示全部楼层
本楼: 👍   100% (3)
 
 
0% (0)   👎
全局: 👍   95% (9796)
 
 
4% (422)    👎
C++ version
游客,本帖隐藏的内容需要积分高于 100 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.


补充内容 (2019-5-18 06:24):
输出
3
5
6
7
8
12
13
14
-1
-1
-1
-1
-1
-1
-1
-1

评分

参与人数 3大米 +5 收起 理由
riptide22 + 1 赞一个
买了拿铁 + 1 赞一个
tinlittle + 3 没有废话的代码,谢谢参与

查看全部评分

回复

使用道具 举报

我的人缘0
yeetatbig4 2019-5-17 06:01:38 | 显示全部楼层
本楼: 👍   100% (3)
 
 
0% (0)   👎
全局: 👍   95% (2192)
 
 
4% (109)    👎
哎,要提升看python的能力了,java刷习惯了,看python好生不习惯。。。但看了半天终于看懂了!
我觉得 `return nums[end] - nums[start] - (end - start)` 这一步挺妙的,当场提示我用二分法的话,我若想不到这一步,还是解不出来。回去后我补个java版本的解法。谢谢楼主分享

去Fiverr找HR修改简历

去Fiverr找HR修改简历!
            
回复

使用道具 举报

我的人缘0
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   98% (3019)
 
 
1% (57)    👎
这个题是中等难度,看来地里新农入门者多,当初设200分高了点。待回有电脑了,再重发个120分的

评分

参与人数 2大米 +2 收起 理由
marshallzh + 1 给你点个赞!
miluChen + 1 赞一个

查看全部评分

回复

使用道具 举报

我的人缘0
wangbd 2019-5-21 04:38:09 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   94% (84)
 
 
5% (5)    👎
Tina_Qity 发表于 2019-5-17 12:41
发个java的,请指点
[mw_shl_code=java,true]public int findKthMissing(int[] nums, int k) {
        i ...

多谢分享,

我总结了一下这个代码的思路,各位大神可以指点。

  思路, 二分查找:
  1. 先表明每个数组里面数字的下标[2(0),4(1),7(2),8(3),9(4),15(5)]。
  2. 因为数组是排过序的,所以任意两个数字之差 + 1 就代表了这两个数字中间应该有多少个数字。比如原数组中 2 到 7 之间有6个数。
     这些数字分别是 [2, 3, 4, 5, 6, 7], 正好是 7 - 2 + 1 = 6。
  3. 因为数组是排过序的,所以任何两个数的下标之差 + 1 就代表了这个两个数字中间实际有多少个数字。 比如原数组中 2(0) 到 7 (2) 之间有3个数。
     这些数字分别是 [2(0),4(1),7(2)], 正好是2 - 0 + 1 = 4。
  4. 我们分别可以求到两个数中应该有多少个数字nums[j] - nums + 1, 和两个数中实际有多少个数字j - i + 1, 用应该有的数字个数-实际有的
      数字个数 = 虚拟数组个数(virtual), 这样我们就能慢慢找到第k个数。
  5. 在二分查找时,我们有left变量指向数组最左边,和right变量指向数组最右边,和middle变量指向数组中间。 我们最开始假设left和right下标中间一定
      有大于等于k个虚拟数组,然后慢慢缩小查找范围到第k个虚拟数。
  6. 如果我们先求left和middle的虚拟数组个数 virtual = (nums[middle] - nums[left] + 1) - (middle - left + 1)
  7. 如果virtual小于k,表示我们找到了过少的虚拟数组,找打了前virtual个数, 然后继续向右二分搜索剩下的virtual -= k, left = middle,virtual -= k
  8. 如果virtual大于k,表示我们找到了太多的虚拟数组,需要缩小搜索范围,right = middle, 完成二分搜索
回复

使用道具 举报

我的人缘0
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   100% (28)
 
 
0% (0)    👎
赞一个,感觉核心就是能在O(1)时间内得出数组中两个index间miss了多少number,这样就可以用平常的二分法O(logn)求解了
回复

使用道具 举报

我的人缘0
 楼主| tinlittle 2019-5-17 03:51:11 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   98% (3019)
 
 
1% (57)    👎
小狗雪碧 发表于 2019-5-16 11:59
感谢分享!我有一个问题,这个非递归的方法。对于while循环的终止条件,为什么start + 1 != end 呢?

因为是要找一个range呀,漏掉的数一定是在给出的两个数之间。你要是用start<=end就不对了。

也许你是问为什么不是start+1 < end?那个也对。这个是个人习惯,start+1 != end 逻辑上更精确。要纠结的话,推荐用start+1 < end,这个更好记,遇到极端初始条件不容易错。
回复

使用道具 举报

我的人缘0
小狗雪碧 2019-5-17 02:59:49 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (160)
 
 
3% (5)    👎
tinlittle 发表于 2019-5-16 13:28
加一个简短的,大家更熟悉的非递归实现:
**** 本内容被作者隐藏 ****

感谢分享!我有一个问题,这个非递归的方法。对于while循环的终止条件,为什么start + 1 != end 呢?
回复

使用道具 举报

我的人缘0
小狗雪碧 2019-5-17 06:57:37 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   96% (160)
 
 
3% (5)    👎
tinlittle 发表于 2019-5-17 03:51
因为是要找一个range呀,漏掉的数一定是在给出的两个数之间。你要是用start

太感谢了!“漏掉的数字一定是在给出的两个数字之间”  这句话点醒了我!!! 楼主以后要多发刷题笔记啊!
回复

使用道具 举报

我的人缘0
wisdompeak2 2019-5-17 09:13:18 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (251)
 
 
0% (1)    👎
这个题在地里的面经经常出现,我大概看过三次吧。
随手找到其中一个:http://www.1point3acres.com/bbs/ ... sortid%3D311%26sear
choption%5B3089%5D%5Bvalue%5D%5B3%5D%3D3%26searchoption%5B3089%5D%5Btype%5D%3Dcheckbox%26searchoption%5B3046
%5D%5Bvalue%5D%3D1%26searchoption%5B3046%5D%5Btype%5D%3Dradio%26sortid%3D311

补充内容 (2019-5-17 09:20):
不好意思,这个链接贴出来的时候broken了。。。
这个可以用:https://www.1point3acres.com/bbs ... read&tid=443454

评分

参与人数 2大米 +18 收起 理由
wyzhang + 2 给你点个赞!
admin + 16

查看全部评分

回复

使用道具 举报

我的人缘0
 楼主| tinlittle 2019-5-17 11:16:19 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (3019)
 
 
1% (57)    👎
zbh9000510 发表于 2019-5-16 15:01
哎,要提升看python的能力了,java刷习惯了,看python好生不习惯。。。但看了半天终于看懂了!
我觉得 `re ...

好啊,欢迎补充Java版,传上来给你加米。
回复

使用道具 举报

我的人缘0
 楼主| tinlittle 2019-5-17 11:21:09 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   98% (3019)
 
 
1% (57)    👎
wisdompeak2 发表于 2019-5-16 18:13
这个题在地里的面经经常出现,我大概看过三次吧。
随手找到其中一个:http://www.1point3acres.com/bbs/fo ...

老哥眼力和记性都强。搜索引擎是比不上人民雪亮的眼睛啊。
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 注册账号

本版积分规则

隐私提醒:
■为防止被骚扰甚至人肉,不要公开留微信等联系方式,请以论坛私信方式发送。
■特定版块可以超级匿名:https://pay.1point3acres.com/tools/thread
■其他版块匿名方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|||一亩三分地

GMT+8, 2020-5-25 05:23

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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