9

我参加了一家高频交易公司的面试。他们问我一个算法O(n)：

  • 给定n空间点
  • 给定一个散列函数，它返回平面中的点O(1)，
  • 找到一个覆盖空间中最多点的最佳匹配圆。

要求：

  • 圆心必须有整数坐标，它的半径是3。
  • 圆内的点不一定有整数坐标

我用谷歌搜索并做了一些研究。有一个O(n) 算法（来自普林斯顿大学的 Chazelle 的最佳圆圈放置），但它有点超出我的理解水平，并在 10 分钟内将其放在一起解释它。我已经知道O(n^2)和O(n^3)算法。

请帮我找到一个O(n)算法。

4

2 回答 2

8

我猜整数坐标约束显着简化了问题。这对我来说看起来像 O(n)：

- 制作空间中所有整数点的字典，并将条目设置为 0。

- 对于每个数据点，找到半径 3 内的整数点，并将字典的相应条目加 1。这样做的原因是，可以作为该特定数据点所在的圆心的点集是围绕该数据点具有相同半径的圆的整数限制。可以对位于长度为 6 的正方形上的所有点进行搜索（认为并非所有点都需要明确评估，因为内接超立方体内的这些点肯定在里面）。

- 返回对应于字典最大值的整数点，即大多数数据点在圆内的中心。

编辑：我猜有些代码比解释更好。这是使用 numpy 和 matplotlib 工作的 python。阅读起来应该不会太难：

# -*- coding: utf-8 -*-
"""
Created on Mon Mar 11 19:22:12 2013

@author: Zah
"""

from __future__ import division
import numpy as np
import numpy.random
import matplotlib.pyplot as plt
from collections import defaultdict
import timeit
def make_points(n):
    """Generates n random points"""
    return np.random.uniform(0,30,(n,2))

def find_centers(point, r):
    """Given 1 point, find all possible integer centers searching in a square 
    around that point. Note that this method can be imporved."""
    posx, posy = point
    centers = ((x,y) 
        for x in xrange(int(np.ceil(posx - r)), int(np.floor(posx + r)) + 1)
        for y in xrange(int(np.ceil(posy - r)), int(np.floor(posy + r)) + 1)        
        if (x-posx)**2 + (y-posy)**2 < r*r)
    return centers


def find_circle(n, r=3.):
    """Find the best center"""
    points = make_points(n)
    d = defaultdict(int)
    for point in points:
        for center in find_centers(point, r):
            d[center] += 1
    return max(d , key = lambda x: d[x]), points

def make_results():
    """Green circle is the best center. Red crosses are posible centers for some
    random point as an example"""
    r = 3
    center, points = find_circle(100)
    xv,yv = points.transpose()
    fig = plt.figure()
    ax = fig.add_subplot(111)
    ax.set_aspect(1)
    ax.scatter(xv,yv)
    ax.add_artist(plt.Circle(center, r, facecolor = 'g', alpha = .5, zorder = 0))
    centersx, centersy  = np.array(list(find_centers(points[0], r))).transpose()
    plt.scatter(centersx, centersy,c = 'r', marker = '+')
    ax.add_artist(plt.Circle(points[0], r, facecolor = 'r', alpha = .25, zorder = 0))
    plt.show()

if __name__ == "__main__":
    make_results()

结果： 结果图 绿色圆圈是最好的，红色的东西展示了如何为某个随机点挑选中心。

In [70]: %timeit find_circle(1000)
1 loops, best of 3: 1.76 s per loop

In [71]: %timeit find_circle(2000)
1 loops, best of 3: 3.51 s per loop

In [72]: %timeit find_circle(3000)
1 loops, best of 3: 5.3 s per loop

In [73]: %timeit find_circle(4000)
1 loops, best of 3: 7.03 s per loop

在我非常慢的机器上。行为显然是线性的。

于 2013-03-09T01:32:02.180 回答
4

有一个不同于（1）中所述的想法，它将要检查的圆圈数量减少到O(n)

关键发现： - 对于一个数据点 p，应该只有有限数量的半径为 3 的圆可以包含数据点 p！换句话说：具有（1st）半径3（2nd）整数作为中心点坐标和（3rd）包含一个特定数据点的圆的数量是O（1）！

关键思想： 迭代所有半径为 3 的潜在圆，并为每个圆计算它将包含的数据点的数量。

算法： - 我们初始化一个空哈希表 h，它映射一个圆中心点 - 即 (i,j) 的组合，其中 i 和 j 都是整数 - 到整数

- For data point p_i in p_1 ... p_n // this loop takes O(n)
    - determine all the centerpoints c_1, c_2 ... c_k of circles which 
      can include p_i (in O(1))
    - for each centerpoint c_j in c_1... c_k // this loop takes O(1)
       - lookup if there is an entry hashtable i.e. test h[c_j]==nil
       - if h[c_j]==nil then h[c_j]:=1 end
       - else h[c_j] := h[c_j] +1 end
    - end for 
 end for

// 最后一个最大值确定需要 O(n) - 遍历 h 中的所有 c_k - 确定键 c_max，其中 h_[c_max] 是 h 中的最大值

你怎么看？欢迎任何意见。

于 2013-03-10T03:35:55.760 回答