Facebook 电面2道题

edyyy 发表于 2017-6-10 07:56
第二题  用heap 是让你用priority_queue之类的吗？我怎么觉得复杂度还是n?

忘了提 他刚开始让我返回最大距离值 后来让我返回坐标 我就说用map 然后排序 针对map排序的优化是用heap

oldman09 发表于 2017-6-11 05:28
minHeap 里有compare function？楼主的意思是不是override priorityqueue用的comparactor？

就是把计算距离这步放到heap里做 就是heap.push(x, y)

forteller 发表于 2017-6-10 08:53
第二题能不能详细说说。谢谢。排序的？不排序的？不排序还能比O(N)低是怎么个意思？

不是sorted的 看前面我的回复

Hertzrun 发表于 2017-6-12 11:49
面试官让提高时间复杂度

还是没太懂
是求一个值，还是就最远的TOP K个值?

第二题没法比O(N)更快把，loop一遍的同时keep track of 最大距离和相对应的(x,y)不就可以了？楼主能再仔细讲下第二位为啥要heap么

用heap是为了求top k!!居然忘了说这点。。。。

heap top k 是很经典的lc的题目吧

可以用priorityqueue嘛？还是要自己写heap？

感谢楼主面筋！