小编use*_*873的帖子

我正在接受一家高频交易公司的采访.他们问我一个算法O(n):

• 给出n空间点
• 给定一个返回平面点的哈希函数O(1),
• 找到覆盖空间中最多点的最佳匹配圆.

要求:

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

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

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