Uber Phone

倒序浏览 · 2021-12-16 07:13:46

您需要登录才可以下载或查看附件。没有帐号？注册账号

x

面到了一个没见过的题给了一堆点让找到相互之间距离小于threshold的pair time

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

{2, 1}}
现场没想出来如何做到好于O(n^2)

frandblinkc

这是个经典问题 fixed radius nearest neighbors.

用2D bucketing (算法叫Cell Listing), 假设homogenous distribution的情况下可以做到O(N), 但是worst-case还是 O(N^2)

求加米!

参考:
https://www.wikiwand.com/en/Cell_lists

https://jaantollander.com/post/s ... guage/#introduction

tiantiana · 2021-12-28 07:09:13

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

tiantiana · 2021-12-28 04:49:06

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

来自APP · 2021-12-16 08:25:54

假设所有pair都是valid 那输出结果就是大小O(N ^ 2) 了。怎么好于这个呢？有大神指点吗

ciacia7621 · 2021-12-16 11:23:38

对我觉得worst case还是n方，但可能有些地方可以稍微优化一下

Jsmilth · 2021-12-28 05:40:07

tiantiana 发表于 2021-12-27 15:49
这题应该可以好过n方的。
- sort array by the distance between each （O n（lgN））
- go through the ...

问下楼主，计算每两个点distance的时候不就是需要n方吗

匿名用户-53JHO *2022-1-9 13:28:05* · 2022-1-9 13:28:05

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

Wwwyyy

tiantiana 发表于 2021-12-27 12:49
这题应该可以好过n方的。
- sort array by the distance between each （O n（lgN））
- go through the ...

看题描述是二维的，这个就没法按照distance sort了吧

fhx200622

如果二维情况，可以先遍历一边找出最最下角的点再sort