LeetCode 973「最接近原点的 K 个点」多解法详解：排序、堆与 QuickSelect 的工程权衡-北京尧图网络

LeetCode 973「最接近原点的 K 个点」多解法详解排序、堆与 QuickSelect 的工程权衡【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本篇技术指南以 articles/k-closest-points-to-origin.md 为核心骨架系统讲解 LeetCode 973「K Closest Points to Origin」的四种主流解法全量排序、最小堆、容量为 k 的最大堆以及 QuickSelect。文章同时结合本仓库在 Python、Java、C、Go、Rust、JavaScript、Kotlin、Swift、C 等多语言下的真实实现如 python/0973-k-closest-points-to-origin.py、cpp/0973-k-closest-points-to-origin.cpp逐层印证算法原理与复杂度结论。读完你不仅能熟练 AC 该题还能掌握「Top-K 问题」在面试与工程中的通用选型方法论。问题定义与前置知识给定一个二维点数组points其中points[i] [x_i, y_i]以及一个整数k返回距离原点(0, 0)最近的k个点。注意返回顺序不作要求答案唯一性由距离保证。开始动手前你需要先熟悉以下四块基础能力原文档将其列为 Prerequisites自定义比较器排序Sorting with Custom Comparators不是按元素本身排序而是按某个计算值这里是距离排序欧几里得距离Euclidean Distance点到原点的距离为sqrt(x^2 y^2)而平方距离与真实距离单调等价可直接用x^2 y^2参与比较堆数据结构Heap利用最小堆与最大堆高效追踪最大/最小元素QuickSelect 算法借助数组分区在平均 O(n) 时间内找到第 k 个元素无需完整排序。解法一全量排序Sorting思路要找到距离原点最近的k个点最直观的做法是按距离对所有点排序。真实距离需要开平方根而平方根函数是单调递增的因此sqrt(d1) sqrt(d2)等价于d1 d2。比较时直接用平方距离[ d^2 x^2 y^2 ]既省去开方计算又避免浮点数精度问题且不改变相对顺序。算法步骤对每个点(x, y)计算平方距离dist x^2 y^2按该dist值对全部点排序返回排序后列表的前k个点。多语言实现class Solution: def kClosest(self, points: List[List[int]], k: int) - List[List[int]]: points.sort(keylambda p: p[0]**2 p[1]**2) return points[:k]public class Solution { public int[][] kClosest(int[][] points, int k) { Arrays.sort(points, (a, b) - (a[0] * a[0] a[1] * a[1]) - (b[0] * b[0] b[1] * b[1])); return Arrays.copyOfRange(points, 0, k); } }class Solution { public: vectorvectorint kClosest(vectorvectorint points, int k) { sort(points.begin(), points.end(), [](const auto a, const auto b) { return (a[0] * a[0] a[1] * a[1]) (b[0] * b[0] b[1] * b[1]); }); return vectorvectorint(points.begin(), points.begin() k); } };class Solution { /** * param {number[][]} points * param {number} k * return {number[][]} */ kClosest(points, k) { points.sort((a, b) a[0] ** 2 a[1] ** 2 - (b[0] ** 2 b[1] ** 2)); return points.slice(0, k); } }public class Solution { public int[][] KClosest(int[][] points, int k) { Array.Sort(points, (a, b) (a[0] * a[0] a[1] * a[1]).CompareTo(b[0] * b[0] b[1] * b[1])); return points[..k]; } }func kClosest(points [][]int, k int) [][]int { sort.Slice(points, func(i, j int) bool { return points[i][0]*points[i][0] points[i][1]*points[i][1] points[j][0]*points[j][0] points[j][1]*points[j][1] }) return points[:k] }class Solution { fun kClosest(points: ArrayIntArray, k: Int): ArrayIntArray { points.sortBy { it[0] * it[0] it[1] * it[1] } return points.take(k).toTypedArray() } }class Solution { func kClosest(_ points: [[Int]], _ k: Int) - [[Int]] { return points.sorted { ($0[0] * $0[0] $0[1] * $0[1]) ($1[0] * $1[0] $1[1] * $1[1]) } .prefix(k) .map { $0 } } }impl Solution { pub fn k_closest(mut points: VecVeci32, k: i32) - VecVeci32 { points.sort_by_key(|p| p[0] * p[0] p[1] * p[1]); points.truncate(k as usize); points } }仓库中的 javascript/0973-k-closest-points-to-origin.js 把「自定义比较器前 k 个切片」拆成两个意图清晰的函数squaredDistance负责计算平方距离主函数负责排序与切片是工程化写法的一个好示范。复杂度时间复杂度$O(n \log n)$空间复杂度$O(1)$ 或 $O(n)$取决于具体排序算法的实现原地排序如 Timsort 视语言而定。解法二最小堆Min-Heap思路最小堆总是把最小的元素放在堆顶。若把所有点按平方距离作为优先级插入最小堆那么堆顶始终是当前最近的点弹出顺序即由近及远。因此连续弹出k次就得到k个最近点。算法步骤对每个点(x, y)计算平方距离x^2 y^2以(distance, x, y)形式入堆。用一次heapify建堆或逐个 push。循环k次弹出堆顶最小元素将其(x, y)加入结果。返回结果列表。多语言实现class Solution: def kClosest(self, points: List[List[int]], k: int) - List[List[int]]: minHeap [] for x, y in points: dist (x ** 2) (y ** 2) minHeap.append([dist, x, y]) heapq.heapify(minHeap) res [] while k 0: dist, x, y heapq.heappop(minHeap) res.append([x, y]) k - 1 return respublic class Solution { public int[][] kClosest(int[][] points, int K) { PriorityQueueint[] minHeap new PriorityQueue(Comparator.comparing(a - a[0])); for (int[] point : points) { int dist point[0] * point[0] point[1] * point[1]; minHeap.offer(new int[]{dist, point[0], point[1]}); } int[][] result new int[K][2]; for (int i 0; i K; i) { int[] point minHeap.poll(); result[i] new int[]{point[1], point[2]}; } return result; } }class Solution { public: vectorvectorint kClosest(vectorvectorint points, int K) { auto comp [](const vectorint a, const vectorint b) { return a[0]*a[0] a[1]*a[1] b[0]*b[0] b[1]*b[1]; }; priority_queuevectorint, vectorvectorint, decltype(comp) minHeap(comp); for (const auto point : points) { minHeap.push({point[0], point[1]}); } vectorvectorint result; for (int i 0; i K; i) { result.push_back(minHeap.top()); minHeap.pop(); } return result; } };/** * const { MinPriorityQueue } require(datastructures-js/priority-queue); */ class Solution { /** * param {number[][]} points * param {number} k * return {number[][]} */ kClosest(points, k) { const minHeap new MinPriorityQueue((point) point[0]); for (const [x, y] of points) { const dist x ** 2 y ** 2; minHeap.enqueue([dist, x, y]); } const res []; for (let i 0; i k; i) { const [_, x, y] minHeap.dequeue(); res.push([x, y]); } return res; } }public class Solution { public int[][] KClosest(int[][] points, int K) { PriorityQueueint[], int minHeap new PriorityQueueint[], int(); foreach (int[] point in points) { int dist point[0] * point[0] point[1] * point[1]; minHeap.Enqueue(new int[] { dist, point[0], point[1] }, dist); } int[][] result new int[K][]; for (int i 0; i K; i) { int[] point minHeap.Dequeue(); result[i] new int[] { point[1], point[2] }; } return result; } }type MinHeap [][]int func (h MinHeap) Len() int { return len(h) } func (h MinHeap) Less(i, j int) bool { return h[i][0] h[j][0] } func (h MinHeap) Swap(i, j int) { h[i], h[j] h[j], h[i] } func (h *MinHeap) Push(x interface{}) { *h append(*h, x.([]int)) } func (h *MinHeap) Pop() interface{} { old : *h n : len(old) x : old[n-1] *h old[:n-1] return x } func kClosest(points [][]int, k int) [][]int { minHeap : MinHeap{} heap.Init(minHeap) for _, point : range points { x, y : point[0], point[1] dist : x*x y*y heap.Push(minHeap, []int{dist, x, y}) } res : [][]int{} for i : 0; i k; i { point : heap.Pop(minHeap).([]int) res append(res, []int{point[1], point[2]}) } return res }class Solution { fun kClosest(points: ArrayIntArray, k: Int): ListIntArray { val minHeap PriorityQueue(compareByIntArray { it[0] * it[0] it[1] * it[1] }) for (point in points) { minHeap.add(point) } val res mutableListOfIntArray() repeat(k) { res.add(minHeap.poll()) } return res } }struct Item: Comparable { let dist: Int let x: Int let y: Int static func (lhs: Item, rhs: Item) - Bool { return lhs.dist rhs.dist } } class Solution { func kClosest(_ points: [[Int]], _ k: Int) - [[Int]] { var minHeap HeapItem() for point in points { let x point[0], y point[1] let dist x * x y * y minHeap.insert(Item(dist: dist, x: x, y: y)) } var res [[Int]]() for _ in 0..k { if let item minHeap.popMin() { res.append([item.x, item.y]) } } return res } }impl Solution { pub fn k_closest(points: VecVeci32, k: i32) - VecVeci32 { let mut heap BinaryHeap::new(); for p in points { let dist p[0] * p[0] p[1] * p[1]; heap.push(Reverse((dist, p[0], p[1]))); } let mut res Vec::new(); for _ in 0..k { if let Some(Reverse((_, x, y))) heap.pop() { res.push(vec![x, y]); } } res } }仓库源码印证python/0973-k-closest-points-to-origin.py 是仓库中的最小堆实现先heapq.heapify(minHeap)以 O(n) 线性建堆再弹出 k 次与文档描述的「heapify 建堆」路径完全一致cpp/0973-k-closest-points-to-origin.cpp 展示了 C 的greatervectorint构造利用priority_queue的迭代器区间构造函数直接以 O(n) 建堆源码注释明确标注 This constructor takes O(n) timego/0973-k-closest-points-to-origin.go 通过实现heap.Interface的Len/Less/Swap/Push/Pop五个方法完成最小堆Less按dist升序比较随后heap.Init建堆、heap.Pop弹出 k 次rust/0973-k-closest-points-to-origin.rs 巧妙复用 Rust 标准库的BinaryHeap默认最大堆用std::cmp::Reverse反转比较方向实现最小堆语义Reverse((dist, x, y))元组同时充当了「距离坐标」的复合载荷swift/0973-k-closest-points-to-origin.swift 则手写了一个基于数组索引的Heap类heapifypop维护堆序适合不依赖第三方库的 Swift 环境。复杂度时间复杂度用heapify建堆为 $O(n k \cdot \log n)$若逐点 push 则为 $O(n \cdot \log n k \cdot \log n)$空间复杂度$O(n)$其中 $n$ 为数组points的长度。解法三容量为 k 的最大堆Max-Heap思路我们只需要k个最近点并不需要全量排序。改用容量固定为 k 的最大堆堆内始终保存当前已见过的 k 个最近点距离最大的点位于堆顶遇到比堆顶当前最远候选更近的新点时弹出堆顶、插入新点。这样堆的规模永远不会超过 k且始终维护 k 个最优候选从 O(n) 空间降到 O(k)。算法步骤创建空最大堆。遍历每个点计算平方距离d x^2 y^2将(d, point)入堆若堆大小超过k弹出距离最大的元素。遍历结束后堆中恰好是k个最近点。返回堆中全部点。多语言实现class Solution: def kClosest(self, points: List[List[int]], k: int) - List[List[int]]: maxHeap [] for x, y in points: dist -(x ** 2 y ** 2) heapq.heappush(maxHeap, [dist, x, y]) if len(maxHeap) k: heapq.heappop(maxHeap) res [] while maxHeap: dist, x, y heapq.heappop(maxHeap) res.append([x, y]) return resPython 的heapq只有最小堆这里用取负距离的技巧把「最大值」变成「最小值」从而用最小堆模拟最大堆。public class Solution { public int[][] kClosest(int[][] points, int k) { PriorityQueueint[] maxHeap new PriorityQueue( (a, b) - Integer.compare(b[0] * b[0] b[1] * b[1], a[0] * a[0] a[1] * a[1]) ); for (int[] point : points) { maxHeap.offer(point); if (maxHeap.size() k) { maxHeap.poll(); } } int[][] res new int[k][2]; int i 0; while (!maxHeap.isEmpty()) { res[i] maxHeap.poll(); } return res; } }class Solution { public: vectorvectorint kClosest(vectorvectorint points, int k) { priority_queuepairint, pairint, int maxHeap; for (auto point : points) { int dist point[0] * point[0] point[1] * point[1]; maxHeap.push({dist, {point[0], point[1]}}); if (maxHeap.size() k) { maxHeap.pop(); } } vectorvectorint res; while (!maxHeap.empty()) { res.push_back({maxHeap.top().second.first, maxHeap.top().second.second}); maxHeap.pop(); } return res; } };/** * const { PriorityQueue } require(datastructures-js/priority-queue); */ class Solution { /** * param {number[][]} points * param {number} k * return {number[][]} */ kClosest(points, k) { const maxHeap new PriorityQueue((a, b) b[0] - a[0]); for (const [x, y] of points) { const dist x ** 2 y ** 2; maxHeap.push([dist, x, y]); if (maxHeap.size() k) { maxHeap.pop(); } } const res []; while (maxHeap.size() 0) { let tmp maxHeap.pop(); res.push([tmp[1], tmp[2]]); } return res; } }public class Solution { public int[][] KClosest(int[][] points, int K) { PriorityQueueint[], int maxHeap new(); foreach (var point in points) { int dist point[0] * point[0] point[1] * point[1]; maxHeap.Enqueue(point, -dist); if (maxHeap.Count K) { maxHeap.Dequeue(); } } var res new Listint[](); while (maxHeap.Count 0) { res.Add(maxHeap.Dequeue()); } return res.ToArray(); } }type MaxHeap [][]int func (h MaxHeap) Len() int { return len(h) } func (h MaxHeap) Less(i, j int) bool { return h[i][2] h[j][2] } func (h MaxHeap) Swap(i, j int) { h[i], h[j] h[j], h[i] } func (h *MaxHeap) Push(x interface{}) { *h append(*h, x.([]int)) } func (h *MaxHeap) Pop() interface{} { old : *h n : len(old) x : old[n-1] *h old[:n-1] return x } func kClosest(points [][]int, k int) [][]int { maxHeap : MaxHeap{} heap.Init(maxHeap) for _, point : range points { x, y : point[0], point[1] dist : x*x y*y heap.Push(maxHeap, []int{x, y, dist}) if maxHeap.Len() k { heap.Pop(maxHeap) } } result : make([][]int, k) for i : k - 1; i 0; i-- { point : heap.Pop(maxHeap).([]int) result[i] []int{point[0], point[1]} } return result }class Solution { fun kClosest(points: ArrayIntArray, k: Int): ArrayIntArray { val maxHeap PriorityQueueIntArray { a, b - (b[0] * b[0] b[1] * b[1]) - (a[0] * a[0] a[1] * a[1]) } for (point in points) { maxHeap.offer(point) if (maxHeap.size k) { maxHeap.poll() } } return Array(k) { maxHeap.poll() } } }struct Item: Comparable { let dist: Int let x: Int let y: Int static func (lhs: Item, rhs: Item) - Bool { return lhs.dist rhs.dist } } class Solution { func kClosest(_ points: [[Int]], _ k: Int) - [[Int]] { var maxHeap HeapItem() for point in points { let x point[0], y point[1] let dist x * x y * y maxHeap.insert(Item(dist: dist, x: x, y: y)) if maxHeap.count k { _ maxHeap.popMin() } } var res [[Int]]() while !maxHeap.isEmpty { if let item maxHeap.popMin() { res.append([item.x, item.y]) } } return res } }impl Solution { pub fn k_closest(points: VecVeci32, k: i32) - VecVeci32 { let k k as usize; let mut heap BinaryHeap::new(); for p in points { let dist p[0] * p[0] p[1] * p[1]; heap.push((dist, p[0], p[1])); if heap.len() k { heap.pop(); } } heap.into_iter().map(|(_, x, y)| vec![x, y]).collect() } }仓库源码印证java/0973-k-closest-points-to-origin.java 中同时保留了两个版本注释非常直白地说明了选型理由最小堆版本O(NlogN)全量入堆再取前 k最大堆版本把比较器方向反转注释 only this is changed (swapped)并在q.size() k时q.remove()从而把每次删除的代价从log n降到log k整体O(NlogK)。这与文档「堆大小恒为 k、最远者出堆」的算法描述一一对应是理解两种堆思路差异的最佳对照材料。复杂度时间复杂度$O(n \cdot \log k)$空间复杂度$O(k)$其中 $n$ 为数组points的长度。解法四QuickSelect思路我们只关心「k 个最近点」不要求它们有序。这正是 QuickSelect 的适用场景——复用快速排序的 partition 思想选一个枢轴点pivot将所有点分成两拨比枢轴更近的、比枢轴更远的partition 结束后枢轴落在其最终有序位置p若p k左侧恰好就是 k 个最近点若p k去右半区继续找若p k去左半区继续找。整个过程避免了全量排序平均运行时间为O(N)。算法步骤定义平方距离函数dist x^2 y^2。实现 partition 函数选定枢轴距离重排数组使所有更小距离在左、更大距离在右返回枢轴的最终下标。维护双指针L 0、R n - 1。反复 partition若p k终止若p k令L p 1若p k令R p - 1。结束时数组前k个点即为答案。返回这k个点。多语言实现class Solution: def kClosest(self, points, k): euclidean lambda x: x[0] ** 2 x[1] ** 2 def partition(l, r): pivotIdx r pivotDist euclidean(points[pivotIdx]) i l for j in range(l, r): if euclidean(points[j]) pivotDist: points[i], points[j] points[j], points[i] i 1 points[i], points[r] points[r], points[i] return i L, R 0, len(points) - 1 pivot len(points) while pivot ! k: pivot partition(L, R) if pivot k: L pivot 1 else: R pivot - 1 return points[:k]public class Solution { public int[][] kClosest(int[][] points, int k) { int L 0, R points.length - 1; int pivot points.length; while (pivot ! k) { pivot partition(points, L, R); if (pivot k) { L pivot 1; } else { R pivot - 1; } } int[][] res new int[k][2]; System.arraycopy(points, 0, res, 0, k); return res; } private int partition(int[][] points, int l, int r) { int pivotIdx r; int pivotDist euclidean(points[pivotIdx]); int i l; for (int j l; j r; j) { if (euclidean(points[j]) pivotDist) { int[] temp points[i]; points[i] points[j]; points[j] temp; i; } } int[] temp points[i]; points[i] points[r]; points[r] temp; return i; } private int euclidean(int[] point) { return point[0] * point[0] point[1] * point[1]; } }class Solution { public: vectorvectorint kClosest(vectorvectorint points, int k) { int L 0, R points.size() - 1; int pivot points.size(); while (pivot ! k) { pivot partition(points, L, R); if (pivot k) { L pivot 1; } else { R pivot - 1; } } return vectorstd::vectorint(points.begin(), points.begin() k); } private: int partition(vectorvectorint points, int l, int r) { int pivotIdx r; int pivotDist euclidean(points[pivotIdx]); int i l; for (int j l; j r; j) { if (euclidean(points[j]) pivotDist) { swap(points[i], points[j]); i; } } swap(points[i], points[r]); return i; } int euclidean(vectorint point) { return point[0] * point[0] point[1] * point[1]; } };class Solution { /** * param {number[][]} points * param {number} k * return {number[][]} */ kClosest(points, k) { let L 0, R points.length - 1, pivot points.length; while (pivot ! k) { pivot this.partition(points, L, R); if (pivot k) { L pivot 1; } else { R pivot - 1; } } return points.slice(0, k); } /** * param {number[][]} points * param {number} l * param {number} r * return {number} */ partition(points, l, r) { const pivotIdx r; const pivotDist this.euclidean(points[pivotIdx]); let i l; for (let j l; j r; j) { if (this.euclidean(points[j]) pivotDist) { [points[i], points[j]] [points[j], points[i]]; i; } } [points[i], points[r]] [points[r], points[i]]; return i; } /** * param {number[]} point * return {number} */ euclidean(point) { return point[0] ** 2 point[1] ** 2; } }class Solution { public int[][] KClosest(int[][] points, int k) { int L 0, R points.Length - 1; int pivot points.Length; while (pivot ! k) { pivot Partition(points, L, R); if (pivot k) { L pivot 1; } else { R pivot - 1; } } int[][] res new int[k][]; Array.Copy(points, res, k); return res; } private int Partition(int[][] points, int l, int r) { int pivotIdx r; int pivotDist Euclidean(points[pivotIdx]); int i l; for (int j l; j r; j) { if (Euclidean(points[j]) pivotDist) { Swap(points, i, j); i; } } Swap(points, i, r); return i; } private int Euclidean(int[] point) { return point[0] * point[0] point[1] * point[1]; } private void Swap(int[][] points, int i, int j) { int[] temp points[i]; points[i] points[j]; points[j] temp; } }func kClosest(points [][]int, k int) [][]int { euclidean : func(x []int) int { return x[0]*x[0] x[1]*x[1] } partition : func(points [][]int, l, r int) int { pivotIdx : r pivotDist : euclidean(points[pivotIdx]) i : l for j : l; j r; j { if euclidean(points[j]) pivotDist { points[i], points[j] points[j], points[i] i } } points[i], points[r] points[r], points[i] return i } L, R : 0, len(points)-1 pivot : len(points) for pivot ! k { pivot partition(points, L, R) if pivot k { L pivot 1 } else { R pivot - 1 } } return points[:k] }class Solution { fun kClosest(points: ArrayIntArray, k: Int): ArrayIntArray { val euclidean { x: IntArray - x[0] * x[0] x[1] * x[1] } fun partition(points: ArrayIntArray, l: Int, r: Int): Int { val pivotIdx r val pivotDist euclidean(points[pivotIdx]) var i l for (j in l until r) { if (euclidean(points[j]) pivotDist) { points[i] points[j].also { points[j] points[i] } i } } points[i] points[r].also { points[r] points[i] } return i } var L 0 var R points.size - 1 var pivot points.size while (pivot ! k) { pivot partition(points, L, R) if (pivot k) { L pivot 1 } else { R pivot - 1 } } return points.copyOfRange(0, k) } }class Solution { func kClosest(_ points: [[Int]], _ k: Int) - [[Int]] { var points points func euclidean(_ point: [Int]) - Int { return point[0] * point[0] point[1] * point[1] } func partition(_ l: Int, _ r: Int) - Int { let pivotIdx r let pivotDist euclidean(points[pivotIdx]) var i l for j in l..r { if euclidean(points[j]) pivotDist { points.swapAt(i, j) i 1 } } points.swapAt(i, r) return i } var l 0, r points.count - 1 var pivot points.count while pivot ! k { pivot partition(l, r) if pivot k { l pivot 1 } else { r pivot - 1 } } return Array(points[..k]) } }impl Solution { pub fn k_closest(mut points: VecVeci32, k: i32) - VecVeci32 { let k k as usize; let mut l 0usize; let mut r points.len() - 1; let mut pivot points.len(); while pivot ! k { pivot Self::partition(mut points, l, r); if pivot k { l pivot 1; } else { r pivot - 1; } } points.truncate(k); points } fn partition(points: mut VecVeci32, l: usize, r: usize) - usize { let pivot_dist points[r][0] * points[r][0] points[r][1] * points[r][1]; let mut i l; for j in l..r { let d points[j][0] * points[j][0] points[j][1] * points[j][1]; if d pivot_dist { points.swap(i, j); i 1; } } points.swap(i, r); i } }仓库源码印证javascript/0973-k-closest-points-to-origin.js 的 QuickSelect 采用中点取枢轴策略points[left ((right - left) 1)]并内联了squaredDistance计算该文件还额外提供了一个基于距离的二分查找变体第 67-114 行先预计算每个点的距离数组再对「距离值」做二分把距离不大于 mid 的点批量归入答案适合理解「Top-K 可转化为阈值搜索」的思维cpp/0973-k-closest-points-to-origin.cpp 中保留了一份采用「双指针中点枢轴」的 QuickSelect 注释版本与文档描述的「每次 partition 收窄搜索区间」逻辑互为印证kotlin/0973-k-closest-points-to-origin.kt 提供了递归式QuickSelect 写法lPointer k时终止否则分别递归左半或右半区间边界判断直观。复杂度时间复杂度平均 $O(n)$最坏 $O(n^2)$枢轴选取不佳时退化为每次只排除一个元素。空间复杂度$O(1)$原地分区递归版需考虑递归栈开销。四种解法对比与选型解法时间复杂度空间复杂度是否有序输出适用场景全量排序$O(n \log n)$$O(1)$/O(n)是实现最简单n 不大时首选最小堆$O(n k\log n)$heapify$O(n)$按距离升序弹出需要按距离顺序逐个取最大堆容量 k$O(n \log k)$$O(k)$否n 很大、k 很小流式处理QuickSelect平均 $O(n)$$O(1)$否追求理论最优时间不在乎顺序原文档 articles/k-closest-points-to-origin.md 在 hints/k-closest-points-to-origin.md 中给出的参考目标是达到O(nlogk)时间、O(k)空间即容量为 k 的最大堆方案而文档正文补充的 QuickSelect 则在平均意义下把时间压到 O(n)。工程上一般按「数据规模、是否流式、是否需要有序输出」三点取舍数据一次性给全且规模可控用排序海量流式数据用容量 k 的最大堆对时间极致敏感、可容忍最坏 O(n²) 时用 QuickSelect。常见陷阱Common Pitfalls陷阱一用真实距离开平方根使用sqrt(x^2 y^2)完全没有必要一方面引入浮点运算开销另一方面引入精度误差。由于我们只比较相对大小平方距离x^2 y^2保持同样的序关系且规避了开方成本。仓库中 c/0973-k-closest-points-to-origin.c 恰好保留了一个「教科书式反面教材」其distance函数调用了sqrt而其余语言的实现全部采用平方距离比较两相对照正说明工程实现应优先选用平方距离。陷阱二堆类型选反堆解法中最小堆需要把全部 n 个元素入堆、最后再弹出 k 次空间 O(n)而容量 k 的最大堆天然只保留 k 个最近候选空间 O(k)。把两者混用会导致结果错误或维护了远超需要的元素数量、效率退化。用「最大堆」时切记堆顶是当前 k 个候选中距离最大者新点比它近才替换。陷阱三距离计算的整数溢出当坐标可达 $10^4$ 量级时单坐标平方后约为 $10^8$两个坐标平方之和接近 32 位整型上限约 $2.1 \times 10^9$。在存在溢出隐患的语言中应使用更宽的整数类型如long/i64/BigInt或结合题目约束评估风险确保x^2 y^2的计算不产生回绕。总结「最接近原点的 K 个点」是 Top-K 问题的经典入口四种解法覆盖了「排序、堆、快速选择」三大算法范式全量排序提供 O(n log n) 的最简基线最小堆给出按距离顺序输出的全量方案容量为 k 的最大堆以 O(n log k) 时间和 O(k) 空间成为流式场景的最优工程解QuickSelect 则用平均 O(n) 时间换取理论最优。仓库中 Python、Java、C、Go、Rust、JavaScript、Kotlin、Swift、C 九个语言目录下的0973实现如 python/0973-k-closest-points-to-origin.py、cpp/0973-k-closest-points-to-origin.cpp、java/0973-k-closest-points-to-origin.java完整覆盖了本文四种策略可作为多语言对照与面试背诵的参考蓝本。把握「平方距离替代真实距离」「堆容量即答案规模」「QuickSelect 只排序必要的部分」三条主线即可举一反三解决一批相似题目。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考

LeetCode 973「最接近原点的 K 个点」多解法详解：排序、堆与 QuickSelect 的工程权衡

相关推荐

.NET Profiling API 中 ObjectID 的安全使用时机：GC 阻塞语义、对象移动跟踪与 CORPROF_E_UNSUPPORTED_CALL_SEQUENCE 强制检查

马卡龙色十六进制代码：精准色彩协作的工程实践指南

猫抓cat-catch完全指南：浏览器视频嗅探与M3U8下载，30分钟跑通全流程

更多资讯

使用 Lingo CLI 实现 Markdown 内容本地化：frontmatter 字段翻译与 push/pull 工作流实战

Basilisk航天仿真框架：可编程、可审计的高保真动力学内核

k-skill seoul-weather-risk 行政洞解析设计：如何把「행정동 이름 + 자연어」确定性转换为 ASK Seoul 的 place_id

Notepad-- 跨平台文本编辑器指南：如何在 Windows、Linux、macOS 上三步搞定中文编码与文件对比

AI-Infra-Guard mcp-scan 报告格式化提示词深度解析：format_report 模板的设计、调用链与落地实践

通达信主力建仓指标源码解析与实战优化

今日更新

AWS无服务器应用开发指南：从Lambda到SAM的架构与实践

SpringBoot+Vue人事系统实战：解决HR数据断点与事务一致性

MATLAB手写紧束缚模型计算石墨烯能带结构

本周精选

AI驱动的自动化专利分析平台技术解析

LeetCode-Go 题解：1252. Cells with Odd Values in a Matrix（奇数值单元格计数）双解法剖析

在线答疑系统Java毕设实战：Spring Boot前后端分离与状态流转

本月热门

基于YOLO的焊缝缺陷检测：从数据标注到工业部署全流程实践

分布式服务的决策记录

创业产品的首版范围

读完文章，想聊聊您的网站？