为算法提供n log n时间下限,以检查一组点是否具有特殊点k.
k定义为:
对于A组点,如果对于A中的每个点m,在A中存在点q使得k位于线段mq的中间,这样ak不必属于A.
例如,对于一组四个点(1,0),(0,1),(1,1),(0,0),该集合具有特殊点k =(0.5,0.5).
当他们问我这个时,我完全被扑克所面对,没有想到我的想法.我想它需要一些强大的几何背景.
O(nlogn)解决方案(我仍然不清楚你为什么要寻找一个下限解决方案.你可能只是做一个详尽的检查,然后运行一个nlogn循环以确保下限.不是很困难.我认为你必须意味着上限):
通过平均所有点找到唯一有效的候选点.即总结他们的坐标并除以点数.如果这样的存在,就是这样.如果不存在这样的k,我们将发现在最后一步中找到的点无效.
创建一个新的点阵列(集合),我们将轴移动,使它们以点k为中心.即,如果k =(x k,y k),则点(x,y)将变为(xx k,yy k).根据比率x/y和范数sqrt(x 2 + y 2)对点进行排序.正如下一步所示,这种分类是如何完成无关紧要的,即哪个是主要标准,哪个是次要标准.
我们可以搜索每个点的补码,或者更好,只需遍历数组并验证每两个相邻的点确实是补码.即如果这是一个解决方案,那么这个新数组中的每两个互补点都是(x,y)和(-x,-y)形式,因为我们将轴重新定中心,这意味着它们具有相同的比率("渐变" ")和规范,并在排序之后,必须相邻.
如果k无效,那么我们将在此遍历中得到一个点,并发现它的邻居不是正确/互补的形式==>没有这样的k.
Time =
O(n)用于找到
O(n)用于构建新数组的候选k + ,因为每个新点都可以在O(1)+中计算,
O(nlogn)用于排序+
O(n)用于验证遍历
=O(nlogn)
| 归档时间： |
|
| 查看次数： |
454 次 |
| 最近记录： |