题目重点：返回离原点最近的K个二维点，用大小K的最大堆保留候选，并计输出排序成本。
题意与假设
这道练习题保留了面经中值得训练的核心约束，并将需要澄清的条件单独列出。现场拿到变体时，先和面试官确认这些条件。
- 训练整数二维坐标，0≤K≤N；重复点保留不同输入位置，距离相同选较早输入索引，输出按(distance,index)排序。
- 平方距离与实际距离排序一致，无需sqrt；固定宽度语言需检查平方/加法溢出。
解题路线
- heap顶应该是当前最差候选，因此Python minheap存(-distance,-index)。更大distance或更晚index对应更负元组，位于顶便于替换。
- 堆未满先push，满后新候选若比最差更好则heapreplace，其他跳过。不排序全部N点，K很小时降低工作。K0直接返回防访问heap[0]。
- 堆里保存index，最后按正distance/index排序K项再取原points，保证并列选择和输出合同。heap自身数组顺序不是排序结果。
- 不变量处理每个前缀后heap包含该前缀最佳min(K,prefixSize)个；新点差就不可能进入前K，新点好则仅淘汰最差，归纳成立。
手动走一遍
[(1,1),(-1,-1),(0,2)]，K1前两距离都2，选index0；K2保留前两按索引输出。K=N需全部结果排序，K0空，重复坐标不去重。
Python 参考实现
下面的代码按上文假设实现，适合本地运行并追加自己的测试用例。
代码区可横向滚动；使用键盘时，先聚焦代码区再按方向键查看。
import heapq
def closest_points(points,k):
"""Integer 2D coordinates, repeated points retain separate input indices.
Tie: earliest input index. Output sorted by (squared_distance,index).
"""
if not 0<=k<=len(points):raise ValueError('invalid k')
if k==0:return []
heap=[]
for index,(x,y) in enumerate(points):
entry=(-(x*x+y*y),-index)
if len(heap)<k:heapq.heappush(heap,entry)
elif entry>heap[0]:heapq.heapreplace(heap,entry)
indices=sorted((-i for _,i in heap),key=lambda i:(points[i][0]**2+points[i][1]**2,i))
return [points[i] for i in indices]
复杂度
扫描O(N log(K+1))，输出排序O(K log K)，辅助O(K)并含输出索引。Quickselect期望O(N)选择但若要求最终排序还要O(K log K)，不要忽略输出排序。
易错点与追问
容易失分的边界
- 用普通最小距离堆会淘汰最近点，方向相反。
- K=0不提前处理会读空heap。
继续深挖
- 中心改成任意(x0,y0)只改变距离公式；球面经纬度为何不能直接平方差？
- 如果只返回任意K个且tie无要求，怎样简化索引与排序？
