谷歌昂赛特

heiqilin · 2017-10-16 08:00:03

请问楼主面的加州还是西雅图的啊？

byrlhb · 2017-10-16 09:19:16

qingsong 发表于 2017-10-4 11:44
试着写了下第二题
public int kthSmallestDistance(int[] nums, int k) {
//assume inputs are v ...

这个解法应该是对的

张欣 · 2017-10-16 11:56:37

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

其中d(i, j)是|arr - arr[j]| i和j的遍历尽管排过序不仍然是n^2吗

qingsong · 2017-10-16 13:22:56

张欣发表于 2017-10-16 11:56
其中d(i, j)是|arr - arr[j]| i和j的遍历尽管排过序不仍然是n^2吗

真正的算法是第一和第三步，第二步的d(i, j)是不用计算的，是思考过程，不然你不知道第三步怎么来的。
看下26楼我写的代码你就明白了

qingsong · 2017-10-16 13:23:22

张欣发表于 2017-10-16 11:56
其中d(i, j)是|arr - arr[j]| i和j的遍历尽管排过序不仍然是n^2吗

真正的算法是第一和第三步，第二步的d(i, j)是不用计算的，是思考过程，不然你不知道第三步怎么来的。
看下26楼我写的代码你就明白了

张欣 · 2017-10-16 14:29:32

qingsong 发表于 2017-10-16 13:23
真正的算法是第一和第三步，第二步的d(i, j)是不用计算的，是思考过程，不然你不知道第三步怎么来的。
...

好的，谢谢

magicsets · 2017-10-16 16:14:34

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

magicsets · 2017-10-16 16:14:43

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

zbwc · 2017-10-16 16:37:38

benli333 发表于 2017-10-3 13:19
关键是pair怎么取，worst case应该是O（n^2）.但是geekforgeek有个算法，用二分，，能找出kth smallest d ...

gfg那个解法的复杂度是nlg(max-min)吧？你面试他说的n指的是数组长还是数组里的最大值？

zbwc · 2017-10-16 16:39:15

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

谷歌 昂赛特