如何构造平均O(n)时间复杂度的算法查找n个点中距原点最近的m个点

通用方案：快速选择（Quickselect）算法 #

你不需要对全量数据做完整排序，只需要定位到第m小的距离分界点即可，快速选择刚好可以满足平均O(n)的时间要求：

• 首先做距离计算优化：比较两个点到原点的距离大小时，不需要开根号计算实际欧氏距离，直接用x² + y²的平方距离比较即可，既避免浮点运算误差，又能提升计算效率
• 快速选择核心逻辑：
  1. 每次随机选一个点的平方距离作为基准值，将所有点划分为「平方距离小于基准」「等于基准」「大于基准」三组
  2. 统计前两组的总数量：
     • 如果总数量 >= m，递归处理小于基准的分组即可
     • 如果总数量刚好等于m，直接返回前两组所有点
     • 如果总数量 < m，先保留前两组所有点，再递归处理大于基准的分组，仅需要找剩余数量的点即可
• 该算法平均时间复杂度为O(n)，最坏情况为O(n²)，工程中随机选择基准的前提下，最坏情况出现概率可忽略，性能稳定性很高。

参考实现伪代码 #

import random
def get_k_closest(points: list[tuple[float, float]], m: int) -> list[tuple[float, float]]:
    # 计算点到原点的平方距离
    def calc_sq_dist(point: tuple[float, float]) -> float:
        return point[0] ** 2 + point[1] ** 2
    
    def quickselect(left: int, right: int, target_cnt: int) -> None:
        if left >= right:
            return
        # 随机选基准避免最坏情况
        pivot_idx = random.randint(left, right)
        pivot_dist = calc_sq_dist(points[pivot_idx])
        # 基准暂存到右边界
        points[pivot_idx], points[right] = points[right], points[pivot_idx]
        # 分区操作，小于基准的移到左侧
        split_pos = left
        for i in range(left, right):
            if calc_sq_dist(points[i]) < pivot_dist:
                points[split_pos], points[i] = points[i], points[split_pos]
                split_pos += 1
        # 基准移到分区后的正确位置
        points[split_pos], points[right] = points[right], points[split_pos]
        # 递归处理对应分区
        left_cnt = split_pos - left + 1
        if left_cnt == target_cnt:
            return
        elif left_cnt > target_cnt:
            quickselect(left, split_pos - 1, target_cnt)
        else:
            quickselect(split_pos + 1, right, target_cnt - left_cnt)
    
    quickselect(0, len(points) - 1, m)
    return points[:m]

利用笛卡尔平面特性的优化方案（适合点分布均匀场景） #

如果你的输入点在平面上分布相对均匀，可以用空间网格划分思路进一步降低运算常数：

• 遍历一次所有点，得到所有点的最大平方距离max_sq
• 把0到max_sq的距离区间划分为k个等距桶（k取值可参考n/m，比如m是n的1/20则取20个桶），每个桶对应一个平方距离区间
• 遍历所有点，把点放入对应区间的桶中
• 从距离最小的桶开始累计点数，直到累计数量超过m，前面的桶的点全部保留，最后一个桶只需要取够剩余数量的点即可

内容的提问来源于stack exchange，提问作者Attila1177298