给算法一个 n log n 时间下界,以检查一组点是否有一个特殊点 k。
k 定义为:
for a set A of points, if for every point m in A, there is a point q in A such that k is in the middle of the line segment mq such a k does not have to belong to A.
例如,这个集合有一个特殊点 k = (0.5, 0.5) 用于一组四个点 (1,0), (0,1), (1,1), (0,0)。
当他们问我这个问题时,我完全面无表情,什么也没想到。我猜它需要一些强大的几何背景。
最佳答案
O(nlogn)
解决方案(我仍然不清楚您为什么要寻找下限边界解决方案。您不妨做一个详尽的检查,然后运行一个 nlogn 循环来确保下限.不是很困难。我想你一定是指上界):
通过对所有点进行平均来找到唯一有效的候选点。 IE。将它们的坐标相加并除以点数。如果存在这样的 k,就是它。如果不存在这样的k,我们会发现在最后一步找到的点是无效的。
创建一个新的点数组(集),我们在其中移动轴,使它们以点 k 为中心。 IE。如果k = (xk,yk),一个点(x,y)将变成(x-xk, y-yk 子>)。根据比率 x/y 和范数 sqrt(x2+y2) 对点进行排序。正如下一步所示,如何进行排序并不重要,即哪个是主要标准,哪个是次要标准。
我们可以搜索每个点的补集,或者更好的是,简单地遍历数组并验证每两个相邻点确实是补集。 IE。如果这是一个解决方案,那么这个新数组中的每两个互补点都是 (x,y) 和 (-x,-y) 的形式,因为我们重新居中了我们的轴,这意味着它们具有相同的比率(“梯度” ) 和范数,并且在排序之后,必须相邻。
如果 k 无效,那么我们将在此遍历中到达一个点,并发现它的邻居不是正确/互补形式 ==> 没有这样的 k。
时间=
O(n)
寻找候选人 k +
O(n)
用于构建新数组,因为每个新点都可以在 O(1) +
中计算
O(nlogn)
对于排序 +
O(n)
用于验证遍历
= O(nlogn)
关于在 O(n log n) 时间内找到特殊点 k 的算法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7626813/