求：在不规则空间点集（比较大，300多万个点）中寻找距离某点最近的八个点

首先，我们可以把整个城市的咖啡馆做一次“预处理”。比如，把一个城市分成若干个“格子(grid)”,然后根据用户所在的位置把他放到某一个格子里，只对格子里的咖啡馆进行距离排序。

问题又来了，如果格子大小一样，那么绝大多数结果都可能出现在市中心的一个格子里，而郊区的格子里只有极少的结果。在这种情况下，我们应该把市中心多分出几个格子。更进一步，格子应该是一个“树结构”，最顶层是一个大格——整个城市，然后逐层下降，格子越来越小，这样有利于用户进行精确搜索——如果在最底层的格子里搜索结果不多，用户可以逐级上升，放大搜索范围。

摘自于李开复的文章 算法的力量

因为肯定要算出所有点到指定点的距离,所以时间复杂度不可能低于O(n)这个量级.我觉得成都小P孩的方法不错,空间复杂度只有8,是O(1)级别,可以一试,

我来试试，说一下思路。

构造一个链表。

遍历点集，如果链表长度没有达到8个，或者当前点与指定点的距离小于链表未节点值（即连表中存储的点中与指定点距离最最大者），则将链表末节点删掉，再按从小到大的顺序（距离），将当前点插入连表中。

从链表头到链表未，按距离的由小至大存储 点。

遍历点集完成后，即得到答案。

貌似时间复杂度为O（n），空间复杂度为O（1）

高手啊 再给我俩年让我研究研究

贪心呗