t*s
2 楼
给定二维网格里N个点的坐标，取其中任意一个点，找到所有距离这个点不超过K的坐标
点。
距离的定义是X轴距离+Y轴距离。
点。
距离的定义是X轴距离+Y轴距离。
u*l
3 楼
太逗了。
g*s
4 楼
有优于O(n)的解法？
【在 t*****s 的大作中提到】
: 给定二维网格里N个点的坐标，取其中任意一个点，找到所有距离这个点不超过K的坐标
: 点。
: 距离的定义是X轴距离+Y轴距离。
【在 t*****s 的大作中提到】
: 给定二维网格里N个点的坐标，取其中任意一个点，找到所有距离这个点不超过K的坐标
: 点。
: 距离的定义是X轴距离+Y轴距离。
t*d
5 楼
以给出的点为中心的一个选择45度的正方形，边长k(2)^(1/2),
★ 发自iPhone App: ChineseWeb 7.8
【在 t*****s 的大作中提到】
: 给定二维网格里N个点的坐标，取其中任意一个点，找到所有距离这个点不超过K的坐标
: 点。
: 距离的定义是X轴距离+Y轴距离。
★ 发自iPhone App: ChineseWeb 7.8
【在 t*****s 的大作中提到】
: 给定二维网格里N个点的坐标，取其中任意一个点，找到所有距离这个点不超过K的坐标
: 点。
: 距离的定义是X轴距离+Y轴距离。
t*s
6 楼
如果只求一次解应该没有。但是如果多次求解的话应该有预处理以后缩小单次查找时间
的算法。
【在 g*******s 的大作中提到】
: 有优于O(n)的解法？
的算法。
【在 g*******s 的大作中提到】
: 有优于O(n)的解法？
t*s
7 楼
我可能没说清楚。网格只在概念中存在。有的数据只是N组坐标。
【在 t****d 的大作中提到】
: 以给出的点为中心的一个选择45度的正方形，边长k(2)^(1/2),
:
: ★ 发自iPhone App: ChineseWeb 7.8
【在 t****d 的大作中提到】
: 以给出的点为中心的一个选择45度的正方形，边长k(2)^(1/2),
:
: ★ 发自iPhone App: ChineseWeb 7.8
s*r
8 楼
多次查找的话，先sort 就可以吧
【在 t*****s 的大作中提到】
: 如果只求一次解应该没有。但是如果多次求解的话应该有预处理以后缩小单次查找时间
: 的算法。
【在 t*****s 的大作中提到】
: 如果只求一次解应该没有。但是如果多次求解的话应该有预处理以后缩小单次查找时间
: 的算法。
t*s
9 楼
我当时做出来的就是按照一个轴先排序，然后二分查找到该节点，在该轴上往两边找最
多K个长度。这样预处理是O(nlogn),单次是O(logn)+O(k)。
但是印象中在哪儿看过类似的题，这个好像不是最优解。听面试官的意思这个问题还可
以拓展到多个dimension。
【在 s*******r 的大作中提到】
: 多次查找的话，先sort 就可以吧
多K个长度。这样预处理是O(nlogn),单次是O(logn)+O(k)。
但是印象中在哪儿看过类似的题，这个好像不是最优解。听面试官的意思这个问题还可
以拓展到多个dimension。
【在 s*******r 的大作中提到】
: 多次查找的话，先sort 就可以吧
s*n
10 楼
range search? 用ball tree/kd-tree
相关阅读
SQL一般会考什么？金融码农OfferG签了offer不去什么后果？最弱的T4的包CLRS Exercise 4.4-3真悲剧，onsite前夜发现忘了带皮带【ms面试题】用不均匀的骰子掷出均匀的点数Senior Software Developer 的面试和思考这个behavioral question该怎么回答？分享一道L家设计题又被据了小女请教下 如果leetcode只刷了100题 可以找工作吗？OPT 延期申请从NSC被转到Potomac service center各位每次onsite时候问题都百分之百回答上来没有？弯曲华人有没有人一辈子租房子的 (转载)everstring好像是中国公司？AWS Infra Exercise: Dependency Trees ??请教一道二叉树的题猎头的职位薪水如何？nordstorm datalab怎么样哇