构造一个O(n)平均情况算法，从n个点的列表中找到最近的m个点

Question

我们需要构造一个算法，给定笛卡尔平面上n个点的列表，最接近原点的m点(m不是常数，小于等于n)。这个算法需要在O(n)平均时间内工作，这是我一直在努力的。

我最初的想法是根据每个点到原点的距离对列表进行排序，并从排序列表中选择前$m$个点。然而，我所知道的所有排序算法的平均时间都是0 (nlogn)。有没有别的方法，利用笛卡尔平面的性质?

谢谢你的帮助。

Answer 1

使用QuickSelect算法查找距离原点最近的第m个点。这将把列表划分为最近的m个点，然后是更远的点。