谷歌 昂赛特

第二题是一个merge sort的思路, 将数组分成两部分, 然后two pointer找distance pair. NLogN

不是很明白第二题，难道不是一个binary search吗？新开一个数组，维护到目前位置sorted的结果，然后来一个新数，做二分插入这个数，这个数的前邻和后邻做差和最终结果比较，取最小就是答案了吧。 O（NlgN） 难道我对题目理解错了？

进击的菜鸟 发表于 2017-10-4 09:12
不是很明白第二题，难道不是一个binary search吗？新开一个数组，维护到目前位置sorted的结果，然后来一个 ...

噢 好像是我理解错了 维护这个sorted的结果需要O（N2）

您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
使用VIP即刻解锁阅读权限或查看其他获取积分的方式

游客，您好！
本帖隐藏的内容需要积分高于 100 才可浏览
您当前积分为 0。
VIP即刻解锁阅读权限 或 查看其他获取积分的方式
Unlock interview details and practice with AI
Curated Interview Questions from Top Companies

yyyusa 发表于 2017-10-3 15:27
第二轮是烙印吧？这题在gfg上是最高难度expert级别，难度系数4.2/5

是个美国大姐。。

qingsong 发表于 2017-10-3 16:13
第二轮这么想行不行。
1. 先排序
2. 然后想象有n - 1个有序数组

不好意思，我是楼主，那个账号密码忘了，，我想问，那你第二步，不相当于把所有pair都列出来了么？

进击的菜鸟 发表于 2017-10-4 09:23
是啊 我也觉得先排序，
每个数字转化成（value，index）的pair，然后排序，最小diff只出现在相邻元素之 ...

他不是要最小。他要第k个小，第k个小，可能是两个不相邻的数组成的。。

wtcupup 发表于 2017-10-3 13:28
能求下geeksforgeeks的链接嘛

http://www.geeksforgeeks.org/k-t ... two-elements-array/

kappa123456p 发表于 2017-10-4 09:33
他不是要最小。他要第k个小，第k个小，可能是两个不相邻的数组成的。。

哦哦 我犯迷糊了。。。