最近的一对白点和黑点怎么做？# JobHunting - 待字闺中
c*p
1 楼
平面上一堆白点一堆黑点，找最近的白点和黑点。这个题怎么做？
我说说我的想法：
用2个arraylist分别记录白点黑点坐标。每个白点找它最近的黑点。然后把这些最近的
距离比较。
这个复杂度是O(n^2).
求更好的方法～
我说说我的想法：
用2个arraylist分别记录白点黑点坐标。每个白点找它最近的黑点。然后把这些最近的
距离比较。
这个复杂度是O(n^2).
求更好的方法～
A*i
2 楼
隐约觉得可以用DP来做
和那个三角形问题差不多
和那个三角形问题差不多
c*p
3 楼
哪个三角形？
求三角形问题链接。
【在 A*****i 的大作中提到】
: 隐约觉得可以用DP来做
: 和那个三角形问题差不多
求三角形问题链接。
【在 A*****i 的大作中提到】
: 隐约觉得可以用DP来做
: 和那个三角形问题差不多
k*t
4 楼
感觉想leetcode中Pascal's Triangle那道题啊
【在 A*****i 的大作中提到】
: 隐约觉得可以用DP来做
: 和那个三角形问题差不多
【在 A*****i 的大作中提到】
: 隐约觉得可以用DP来做
: 和那个三角形问题差不多
c*p
5 楼
啊？？请问这个是怎么联系起来的。。。。。
【在 k*******t 的大作中提到】
: 感觉想leetcode中Pascal's Triangle那道题啊
【在 k*******t 的大作中提到】
: 感觉想leetcode中Pascal's Triangle那道题啊
k*t
6 楼
那个也是三角形，而且也用dp啊。不知道对不对，求教牛人出来数清楚点
【在 c********p 的大作中提到】
: 啊？？请问这个是怎么联系起来的。。。。。
【在 c********p 的大作中提到】
: 啊？？请问这个是怎么联系起来的。。。。。
c*p
7 楼
我问的这个问题，是怎么和三角形联系起来的呢？
【在 k*******t 的大作中提到】
: 那个也是三角形，而且也用dp啊。不知道对不对，求教牛人出来数清楚点
【在 k*******t 的大作中提到】
: 那个也是三角形，而且也用dp啊。不知道对不对，求教牛人出来数清楚点
i*t
8 楼
对每个白点 在黑点钟查找最近的 用kd tree 之类的 binary tree
建树 大概 nlogn ?
查找 logn
所以 总的复杂度是 假设 白点个数也是 n
nlogn + logn n = 2nlogn = nlogn
不知道对不对
建树 大概 nlogn ?
查找 logn
所以 总的复杂度是 假设 白点个数也是 n
nlogn + logn n = 2nlogn = nlogn
不知道对不对
c*p
9 楼
什么是kd tree？
【在 i******t 的大作中提到】
: 对每个白点 在黑点钟查找最近的 用kd tree 之类的 binary tree
: 建树 大概 nlogn ?
: 查找 logn
: 所以 总的复杂度是 假设 白点个数也是 n
: nlogn + logn n = 2nlogn = nlogn
: 不知道对不对
【在 i******t 的大作中提到】
: 对每个白点 在黑点钟查找最近的 用kd tree 之类的 binary tree
: 建树 大概 nlogn ?
: 查找 logn
: 所以 总的复杂度是 假设 白点个数也是 n
: nlogn + logn n = 2nlogn = nlogn
: 不知道对不对
i*t
10 楼
就是类似于 bst 但是 多维的
感觉是比较典型的 nearest neighbor search 问题 一般都是 kdtree
【在 c********p 的大作中提到】
: 什么是kd tree？
感觉是比较典型的 nearest neighbor search 问题 一般都是 kdtree
【在 c********p 的大作中提到】
: 什么是kd tree？
c*p
11 楼
哦哦，，，一会看看别人怎么说这个题。。
我还是非常confused
【在 i******t 的大作中提到】
: 就是类似于 bst 但是 多维的
: 感觉是比较典型的 nearest neighbor search 问题 一般都是 kdtree
我还是非常confused
【在 i******t 的大作中提到】
: 就是类似于 bst 但是 多维的
: 感觉是比较典型的 nearest neighbor search 问题 一般都是 kdtree
x*8
12 楼
分而治之？看看这样如何:
1. sort the points based on some axis, to divide them rough to two parts
2. the solution is 1 of the following 4:
a) on the left -> recursive call
b) on the right -> recursive call
c) one black on left, one white on right
d) one white on left, one black on right
3. search of c and d can be constrained by the upper limit we get in a) and
b)
【在 c********p 的大作中提到】
: 哦哦，，，一会看看别人怎么说这个题。。
: 我还是非常confused
1. sort the points based on some axis, to divide them rough to two parts
2. the solution is 1 of the following 4:
a) on the left -> recursive call
b) on the right -> recursive call
c) one black on left, one white on right
d) one white on left, one black on right
3. search of c and d can be constrained by the upper limit we get in a) and
b)
【在 c********p 的大作中提到】
: 哦哦，，，一会看看别人怎么说这个题。。
: 我还是非常confused
e*8
13 楼
这个是bichromatic closest pair问题（是computational geometry里很经典的问题）
。觉得面试问不到这种问题吧，实在太偏了，不是那种人人都应该知道的东西。。。。
当然除非你的方向本来就是computational geometry (或者面试官的背景是
computational geometry -_-||)
几个可以考虑的解法：http://stackoverflow.com/questions/8203576/closest-distance-between-two-pointsdisjoint-set
上面有人说的kd tree，就是种nearest neighbor data structure
。觉得面试问不到这种问题吧，实在太偏了，不是那种人人都应该知道的东西。。。。
当然除非你的方向本来就是computational geometry (或者面试官的背景是
computational geometry -_-||)
几个可以考虑的解法：http://stackoverflow.com/questions/8203576/closest-distance-between-two-pointsdisjoint-set
上面有人说的kd tree，就是种nearest neighbor data structure
l*i
14 楼
what if you have all white on left and all black on right, then a) and b)
tell you nothing about min dist between a black and a white.
and
【在 x****8 的大作中提到】
: 分而治之？看看这样如何:
: 1. sort the points based on some axis, to divide them rough to two parts
: 2. the solution is 1 of the following 4:
: a) on the left -> recursive call
: b) on the right -> recursive call
: c) one black on left, one white on right
: d) one white on left, one black on right
: 3. search of c and d can be constrained by the upper limit we get in a) and
: b)
tell you nothing about min dist between a black and a white.
and
【在 x****8 的大作中提到】
: 分而治之？看看这样如何:
: 1. sort the points based on some axis, to divide them rough to two parts
: 2. the solution is 1 of the following 4:
: a) on the left -> recursive call
: b) on the right -> recursive call
: c) one black on left, one white on right
: d) one white on left, one black on right
: 3. search of c and d can be constrained by the upper limit we get in a) and
: b)
x*y
15 楼
Is there any differene from finding 2 closest points in 2-D space, which is
a classic "divide and conquer" problem?
【在 c********p 的大作中提到】
: 平面上一堆白点一堆黑点，找最近的白点和黑点。这个题怎么做？
: 我说说我的想法：
: 用2个arraylist分别记录白点黑点坐标。每个白点找它最近的黑点。然后把这些最近的
: 距离比较。
: 这个复杂度是O(n^2).
: 求更好的方法～
a classic "divide and conquer" problem?
【在 c********p 的大作中提到】
: 平面上一堆白点一堆黑点，找最近的白点和黑点。这个题怎么做？
: 我说说我的想法：
: 用2个arraylist分别记录白点黑点坐标。每个白点找它最近的黑点。然后把这些最近的
: 距离比较。
: 这个复杂度是O(n^2).
: 求更好的方法～
相关阅读
亚麻存粹是个粪坑， new grad 刚入职4个月惨遭pip2019年过去了一半 大家还好吗跳楼的哥们周三还在电话面试 (转载)小黄人的白主子和油主子在飞机上吸毒干炮 (转载)H1B被雷，转B2，pending期间身份合法吗狗家现在4升5情况如何 ？人际关系处理不好，在公司是不是很尴尬？找人组建start up小组（第一轮recruting结束，谢谢）好的员工是不存在的求购来offer软件工程师旗舰课程视频兼职，到底适不适合年轻的你？h1b transfer大家平时都把自己的简历放在什么地方？刷题看书之余再来bb：华人崛起的根本难题Offer反悔感觉bar很高，没做过或者脑子记不牢的题都悲剧面试和准备用python or c++如何有效反对S.386行动指南【9/21最新版】 (转载)公司中国人多了一定好吗？