美丽的房子

第二轮电面，印度妹子， 听不太清，全程热情。

BQ常规题: 1. talk about your project during internship
                2. the most challenging project

Coding (via CodePair): 给定一个坐标origin和一堆点，返回前K个离origin最近的点。
我的思路1：用map存点和距离的映射关系，sort距离，拿到点。
                  分析时间复杂度：O(n + nlogn(sort)) 。（这里sort的时间我忘了算进去，妹子提醒了一下问sort的复杂度

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

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

老问题：如何找点呢？妹子多次提醒你可以不用map，又说你有heap了就不需要map了。我没想出来不用map怎么搞映射关系。
正确的思路是直接用PQ存点，override compare()。
总结：由于对PQ生疏，跪。

这题用QuickSelect也可以，可以做到O(n)的average case复杂度。


求米～～～～～～～～～～