Facebook onsite

psyclaudeZ 发表于 2014-10-31 06:36
第二题如果不需要结果有序的话堆都用不着……直接上selection algorihtm, 选出跟target差绝对值第k大元素， ...

没错，有个朋友面另外一家公司，要求返回前k小的元素，不许用heap，就要用quickselect。

lz第一题越界了怎么处理，如果比n大就算n吗

linuxcoder 发表于 2014-10-31 08:14
lz第一题越界了怎么处理，如果比n大就算n吗

某个方向越界，就代表不能朝这个方向移动。不好意思，漏了这个信息。

lz多久得到结果回复的？

第二题用找第K个数的方法可能做。。。哎，今天面facebook估计是挂了

psyclaudeZ 发表于 2014-10-31 06:36
第二题如果不需要结果有序的话堆都用不着……直接上selection algorihtm, 选出跟target差绝对值第k大元素， ...

你好， “选出跟target差绝对值第k大元素”　这个怎么实现？

这是哪个办公室啊 CA？

先根据target把数组换成diff (in place).
然后用quick select 找到the kth smallest.
然后再partition
然后恢复数组。

smzfeng 发表于 2014-11-5 05:33
这是哪个办公室啊 CA？

对啊。不过已经跪了。

ccgogo123 发表于 2014-11-7 12:54
对啊。不过已经跪了。

跪的原因是什么？没做出来还是？