一亩三分地

 找回密码 注册账号

扫描二维码登录本站

最近看过此主题的会员


码农求职神器Triplebyte
不用海投
内推多家公司面试

Total Comp Calculator
输入offer信息
系统自动计算每年收入

科技公司如何
用数据分析驱动产品开发
coupon code 250off 立减$250

深入浅出AB Test
从入门到精通
coupon code 250off 立减$250
游戏初创公司招聘工程师、UIUX Designer和游戏策划
坐标湾区
DreamCraft创始团队
招聘游戏开发工程师
查看: 6149|回复: 38
收起左侧

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

    [复制链接] |试试Instant~
我的人缘0

分享帖子到朋友圈
tinlittle 发表于 2019-5-16 13:08:33 | 显示全部楼层 |阅读模式
本楼: 👍   100% (17)
 
 
0% (0)   👎
全局: 👍   98% (2447)
 
 
1% (38)    👎

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

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

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

评分

参与人数 41大米 +142 收起 理由
notavailable + 2 给你点个赞!
lq24 + 1 赞一个
shikezhang + 1 谢谢楼主,已加米!
wz30 + 1 赞一个
GhostZ + 3 很有用的信息!
JoyForce + 2 给你点个赞!
wangbd + 1 很有用的信息!
starzero + 1 给你点个赞!
YQOnTheRoad + 1 赞一个
LuckyGemini + 1 赞一个

查看全部评分


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

本帖被以下淘专辑推荐:

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

评分

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

查看全部评分

回复

使用道具 举报

我的人缘0
Tina_Qity 发表于 2019-5-17 12:41:34 | 显示全部楼层
本楼: 👍   100% (4)
 
 
0% (0)   👎
全局: 👍   100% (33)
 
 
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% (2447)
 
 
1% (38)    👎
回应地里新农,重贴降低隐藏积分限制。
游客,本帖隐藏的内容需要积分高于 120 才可浏览,您当前积分为 0。
查看如何攒积分 Click here for more info.
回复

使用道具 举报

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

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

使用道具 举报

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

使用道具 举报

我的人缘0
pandami 发表于 2019-5-18 06:23:12 | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   90% (921)
 
 
9% (102)    👎
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
 楼主| tinlittle 发表于 2019-5-17 12:16:48 来自一亩三分地官方APP | 显示全部楼层
本楼: 👍   100% (2)
 
 
0% (0)   👎
全局: 👍   98% (2447)
 
 
1% (38)    👎
这个题是中等难度,看来地里新农入门者多,当初设200分高了点。待回有电脑了,再重发个120分的

评分

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

查看全部评分

回复

使用道具 举报

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

使用道具 举报

我的人缘0
 楼主| tinlittle 发表于 2019-5-17 03:51:11 | 显示全部楼层
本楼: 👍   100% (1)
 
 
0% (0)   👎
全局: 👍   98% (2447)
 
 
1% (38)    👎
小狗雪碧 发表于 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% (111)
 
 
3% (4)    👎
tinlittle 发表于 2019-5-16 13:28
加一个简短的,大家更熟悉的非递归实现:
**** 本内容被作者隐藏 ****

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

使用道具 举报

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

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

使用道具 举报

我的人缘0
wisdompeak2 发表于 2019-5-17 09:13:18 | 显示全部楼层
本楼: 👍   0% (0)
 
 
0% (0)   👎
全局: 👍   99% (196)
 
 
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% (2447)
 
 
1% (38)    👎
zbh9000510 发表于 2019-5-16 15:01
哎,要提升看python的能力了,java刷习惯了,看python好生不习惯。。。但看了半天终于看懂了!
我觉得 `re ...

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

使用道具 举报

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

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

使用道具 举报

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

本版积分规则

提醒:发帖可以选择内容隐藏,部分板块支持匿名发帖。请认真读完以下全部说明:

■隐藏内容方法 - 不要多加空格: [hide=200]你想要隐藏的内容比如面经[/hide]
■意思是:用户积分低于200则看不到被隐藏的内容
■可以自行设置积分值,不建议太高(200以上太多人看不到),也不建议太低(那就没必要隐藏了)
■建议只隐藏关键内容,比如具体的面试题目、涉及隐私的信息,大部分内容没必要隐藏。
■微信/QQ/电子邮件等,为防止将来被骚扰甚至人肉,以论坛私信方式发给对方最安全。
■匿名发帖的板块和方法:http://www.1point3acres.com/bbs/thread-405991-1-1.html

手机版|小黑屋|一亩三分地

GMT+8, 2019-7-19 20:01

Powered by Discuz! X3

© 2001-2013 Comsenz Inc. Design By HUXTeam

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