Uber VO K 个最近点：小 K 堆、移动司机与路网距离追问

题意与假设

这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。

• 主问题是静态二维整数点，以欧氏距离平方排序；训练代码返回原输入下标，距离相同则较小下标优先。题目未明确并列规则和输出顺序，这两点是确定性训练约定。
• 0≤K≤N，乘客位置可替换原点。真实路网距离查询属于不同成本模型；不能把欧氏距离当作路网 ETA 的同义词。

解题路线

1. 静态小 K：遍历点时计算与 origin 的平方距离，用大小 K 的大顶堆保留当前 K 个最小 (distance,index)；Python 最小堆放负距离/负下标，堆顶就是最差候选。更近者替换堆顶，最后按距离排序输出。
2. 若 K 接近 N，全排序 O(N log N) 简洁；quickselect 通过 partition 找第 K 个阈值，平均 O(N)、最坏 O(N²)，再按固定并列规则取 K 项。面试应说明结果是否要求有序，因为 quickselect 选出集合后排序输出仍有 O(K log K)。
3. 移动点规模巨大时，不应每次查询全扫；先按地理格索引维护 driverId→最新位置/格子/状态，位置变更更新旧/新格，再按从近到远的格边界下界扩张候选。只有当未扫描格到乘客的最短可能距离已不小于当前第 K 个精确直线距离，才能安全停止。
4. 路网复排时，直线距离是路网长度的下界（同一度量且道路路径不能短于几何直线），但不能随口删掉 99% 候选。先对若干候选求真实路网距离形成当前第 K 个上界；仅当其他候选的几何下界超过此上界，才可安全剪枝。若只是近似查询，则要显式给召回率/漏召风险。
5. 路网 ETA 还依赖实时交通与道路通行，几何距离可做粗筛却不能保证与 ETA 同序。司机位置还要核验时效、可接单状态和查询期间移动造成的版本变化，与 q18 的 proximity service 相接。

手动走一遍

points=[(1,0),(2,0),(-1,0)]、K=2，平方距离 1、4、1，按下标稳定规则返回 [0,2]。把 origin 改成 (2,0)，距离变为 1、0、9，返回 [1,0]。某司机几何距离略远仍可能因道路连通更好而 ETA 更短，不能仅按欧氏 Top K 当最终路网 Top K。

Python 参考实现

下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。

代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。

"""Return exact k nearest static 2D points, tie-breaking by input index."""

import heapq


def k_closest(points: list[tuple[int, int]], k: int,
              origin: tuple[int, int] = (0, 0)) -> list[int]:
    if not 0 <= k <= len(points):
        raise ValueError("k must be in 0..len(points)")
    ox, oy = origin
    # Heap root is the farthest retained point. For ties, larger index is worse.
    heap: list[tuple[int, int]] = []
    for index, (x, y) in enumerate(points):
        distance = (x - ox) ** 2 + (y - oy) ** 2
        entry = (-distance, -index)
        if len(heap) < k:
            heapq.heappush(heap, entry)
        elif k and entry > heap[0]:
            heapq.heapreplace(heap, entry)
    return sorted((-index for _, index in heap),
                  key=lambda index: ((points[index][0] - ox) ** 2
                                     + (points[index][1] - oy) ** 2, index))

复杂度

静态 N 点、小 K 堆遍历 O(N log K)，最终排序 O(K log K)，额外 O(K)；K=0 返回空。移动点系统的位置更新和查询复杂度取决于格密度、查询半径和重排候选数，不能宣称常数复杂度。路网精算 R 个候选需 R 次路径服务成本。

易错点与追问

容易失分的边界

• 把 Python 最小堆直接保留 K 个最近点却未把堆顶设成最远者，替换方向颠倒。
• 欧氏距离开平方增加计算且不改变排序；整数坐标用平方距离即可。
• 固定查当前格和 8 邻格就声称绝不漏 Top K；稀疏区域的第 K 个司机可能更远。
• 以‘直线距离先砍 99%’作为精确路网 Top K 证明；只有基于剩余候选下界与当前精确第 K 名上界的剪枝才安全。

继续深挖

• 若司机每 4 秒更新、客户端每秒查询，格索引如何处理跨格原子更新与过期位置？
• 若路网路径服务昂贵，如何分层批量估算 ETA 并给最终 Top K 的误差界？
• 若要返回所有半径内司机而非 K 个最近司机，索引停止条件与输出规模如何变化？可对照 q18。