刀大湿新鲜面筋

白人小哥面的题目, 用的地里之前出现过的题目
https://www.1point3acres.com/bbs/thread-776987-1-1.html
给一组城市name 坐标x 坐标y 输入一系列query name 返回相同x或者相同y的最近city name
every city name is guaranteed to be unique and no 2 cities will have same coordinates
如果没有则返回\'NONE\'
注意如果有相同的最近的城市，返回alphabet更小的城市
顺利拿到下一轮 求加米哎！

我的做法 复杂度nlog(n)

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

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

[/i][/i][/i]

lz的解法似乎没有排除query city本身？这样岂不是都会返回query city自己吗？因为距离最小是0

JessieShen92 发表于 2021-7-28 12:37
差不多 我是做了HashMap x-> TreeMap
这样就是nlog(n)

明白了 谢谢楼主 祝楼主好运

感谢楼主分享！祝楼主好运。 请问这个题目query name给的是city name吗？ 已知一堆city 的x, y坐标， 比如说 [a, 0, 1] , [b,0,9], [c,0,2] , [d,0,2] 然后query是a， expected output是c,  对吗？ 因为b虽然x=0， 但距离a很远， c,d距离a一样，但c的alphabet更小，所以返回c。

请问楼主多久收到onsite 消息的呀

sunnybegoffers 发表于 2021-7-26 19:20
请问楼主多久收到onsite 消息的呀

我那个当天就收到了回复

荷兰猪肥肥 发表于 2021-7-28 15:20
感谢楼主分享！祝楼主好运。 请问这个题目query name给的是city name吗？ 已知一堆city 的x, y坐标， 比如 ...

是的 而且假设query name 都是存在的city 都是valid的

感谢楼主回复！ 那可以尝试先把x相同的点用hash存起来，y相同的点用hash存起来，然后分别找到跟query name的x和y分别相同的点，求出距离，记录下距离的最小值

荷兰猪肥肥 发表于 2021-7-28 15:32
感谢楼主回复！ 那可以尝试先把x相同的点用hash存起来，y相同的点用hash存起来，然后分别找到跟query name ...

差不多 我是做了HashMap x-> TreeMap<y, city>
这样就是nlog(n)

荷兰猪肥肥 发表于 2021-7-28 15:39
明白了 谢谢楼主 祝楼主好运

蟹蟹！！！

这不应该用quick select 做O(N)么