- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
我正在接受一家高频交易公司的面试。他们问我一个O(n)
的算法:
n
个空间点O(1)
中的平面点,3
。我用谷歌搜索并做了一些研究。有一个O(n) 算法(普林斯顿大学 Chazelle 的最佳圆圈放置),但它有点超出我的水平,无法理解并将其放在一起在 10 分钟内解释。我已经知道 O(n^2)
和 O(n^3)
算法。
请帮我找到一个O(n)
算法。
最佳答案
我想整数坐标约束可以显着简化问题。这对我来说看起来像 O(n):
-制作一个空间中所有整数点的字典,并将条目设置为0。
-对于每个数据点,找到半径为3以内的整数点,并将1添加到字典的相应条目中。这样做的原因是,可以作为特定数据点所在圆心的点集是围绕该数据点具有相同半径的圆的整数限制。搜索可以在长度为 6 的正方形上的所有点上完成(认为并非所有点都需要明确评估,因为内切超立方体内部的点肯定在内部)。
-返回字典最大值对应的整数点,即大部分数据点在圆内的圆心。
编辑:我想一些代码比解释更好。这是 python 与 numpy 和 matplotlib 一起工作。不应该太难读:
# -*- 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
在我非常慢的机器上。行为显然是线性的。
关于algorithm - 找到覆盖空间中最多点的圆,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/15305833/
我知道 C++ 中的 overriding 是什么。但是,是否存在覆盖?如果有,是什么意思? 谢谢。 最佳答案 在 C++ 术语中,您有 覆盖(与类层次结构中的虚拟方法相关)和 重载(与具有相同名称但
我想捕获位于另一个元素下的元素的鼠标事件。 这是我所拥有的示例:http://jsfiddle.net/KVLkp/13/ 现在我想要的是当鼠标悬停在红色方 block 上时蓝色方 block 有黄色
以下报道 here我尝试创建一个带有重叠散点图的箱线图。 但是当我运行时: In [27]: table1.t_in[table1.duration==6] Out[27]: counter 7
有一个 JS Fiddle here , 你能在不克隆到新对象的情况下替换 e.target 吗? 下面重复了那个 fiddle 的听众; one.addEventListener('click',
首先要解决重复的可能性: 我不是询问 Override 是什么、它的含义或 @Override 在 java 文档注释之外。那是我不是问 /**Some JavaDoc Comment*/ @over
我想要高于定义的数组。它存储点及其坐标。 public static List simpleGraph(List nodes) { int numEdges = nodes.size() *
我在 http://olisan.dk/blog/ 有一个博客- 如您所见,有一个 28 像素的高间隙(边距顶部)...在 style.css 中: margin-top: 0; 也被设置为 marg
Vulkan 句柄是指向 struct 的不透明指针,或者只是无符号的 64 位整数,具体取决于 VK_USE_64_BIT_PTR_DEFINES 的值: #if (VK_USE_64_BI
我正在尝试提供一个行为类似于 DataGridTextColumn 的 DataGrid 列,但在编辑模式下有一个附加按钮。我查看了 DataGridTemplateColumn,但似乎更容易将 Da
使用 Django 1.10 我想在用户名中允许\字符,因为我在使用“django.contrib.auth.middleware.RemoteUserMiddleware”的 Windows 环境中
我正在尝试使用 ffmpeg 将 Logo 放入 rtmp 流中。我的 ffmpeg 版本是 ffmpeg version 4.3.1目前在我的复杂过滤器中,我有: ffmpeg -re -i 'v
是否有用于Firebase 3存储的方法/规则来禁用文件更新或覆盖? 我为数据库找到了data.exists(),但没有为存储找到解决方案。 最佳答案 TL; DR:在Storage Security
我有两个 Docker Compose 文件,docker-compose.yml看起来像这样 version: '2' services: mongo: image: mongo:3.2
我需要覆盖 JPA 中的集合表吗?也许有人有想法 public class nationality{ @Embedded @AttributeOverrides({
嗨,我正在使用 WIX 和下面的代码将文件安装到目录中。 我的应用程序的工作方式是用户可以在该目录中复制他们自己的文件,覆盖他们喜欢的内容
我正在尝试为 Lua 中的字符串实现我自己的长度方法。 我已成功覆盖字符串的 len() 方法,但我不知道如何为 # 运算符执行此操作。 orig_len = string.len function
在Scala 2.10.4中,给出以下类: scala> class Foo { | val x = true | val f = if (x) 100 else 200
我想做上面的事情。 我过去覆盖了许多文件...... block ,模型,助手......但这个让我望而却步。 谁能看到我在这里做错了什么: (我编辑了这段代码......现在包括一些建议......
根据javadoc An instance method in a subclass with the same signature (name, plus the number and the ty
我有一段代码,只要有可用的新数据作为 InputStream 就会生成新数据。每次都覆盖同一个文件。有时文件在写入之前变为 0 kb。 Web 服务会定期读取这些文件。我需要避免文件为 0 字节的情况
我是一名优秀的程序员,十分优秀!