网络异常，图片无法展示
|
我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。
（这里，平面上两点之间的距离是欧几里德距离。）
你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。
示例 1：
输入： points = [[1,3],[-2,2]], K = 1 输出： [[-2,2]] 解释： (1, 3) 和原点之间的距离为 sqrt(10)， (-2, 2) 和原点之间的距离为 sqrt(8)， 由于 sqrt(8) < sqrt(10)，(-2, 2) 离原点更近。 我们只需要距离原点最近的 K = 1 个点，所以答案就是 [[-2,2]]。 复制代码
示例 2：
输入： points = [[3,3],[5,-1],[-2,4]], K = 2 输出： [[3,3],[-2,4]] （答案 [[-2,4],[3,3]] 也会被接受。） 复制代码
提示：
1 <= K <= points.length <= 10000-10000 < points[i][0] < 10000-10000 < points[i][1] < 10000
解题思路
本题中每个点到原点的之间的距离为两坐标值的平方和的开方。所以两坐标值的平方和越小，则该点距离原点越近。
所以我们只需要找到坐标轴值平方和最小的 k 个点即可。
sort
可以通过以上信息对输入数组进行降序排序，返回排序后的前 k 个元素组成的数组即可。
代码实现
var kClosest = function(points, k) { // 对输入数组升序排序 points.sort((a,b) => (a[0]*a[0]+a[1]*a[1])-(b[0]*b[0]+b[1]*b[1])) // 返回排序后的前 k 个元素 return points.slice(0,k) }; 复制代码
大顶堆
涉及到要维护最值的问题，都可以利用堆来做。
这里因为要维护前 k 个最小值，所以需要一个大顶堆。
循环输入数组，当堆中元素数量小于 k 个或者当前元素小于堆顶元素的时候，将当前元素插入堆中。
如果插入后堆中元素数量超过 k 个，弹出堆顶元素。
最后返回堆中的元素即可。
代码实现
// 大顶堆 class BigHeap{ constructor(){ this.arr = []; this.size = 0; } // 插入操作 push(item){ this.arr.push(item); this.size++; // 插入后自下向上平衡调整 if(this.size>1){ let cur = this.size-1, parent = (cur-1)>>1; while(cur>0&&compare(this.arr[parent],this.arr[cur])){ [this.arr[parent],this.arr[cur]] = [this.arr[cur],this.arr[parent]] cur = parent,parent = (cur-1)>>1; } } } // 弹出操作 pop(){ this.arr[0] = this.arr.pop(); this.size--; // 弹出后自上向下平衡调整 let cur = 0,childl = 1,childr = 2; while( (childl<this.size&&compare(this.arr[cur],this.arr[childl])) || (childr<this.size&&compare(this.arr[cur],this.arr[childr])) ){ if(childr<this.size&&compare(this.arr[childl],this.arr[childr])){ [this.arr[cur],this.arr[childr]] = [this.arr[childr],this.arr[cur]] cur = childr; }else{ [this.arr[cur],this.arr[childl]] = [this.arr[childl],this.arr[cur]] cur = childl; } childl = cur*2+1,childr = cur*2+2; } } // 获取堆顶元素 top(){ return this.arr[0] } } // compare函数 function compare(a,b){ return (a[0]*a[0]+a[1]*a[1])<(b[0]*b[0]+b[1]*b[1]) } var kClosest = function(points, k) { // 获取大顶堆实例 const heap = new BigHeap(); // 遍历输入数组 for(let i = 0;i<points.length;i++){ // 将前 k 个最小的元素保存在堆中 if(heap.size<k || compare(points[i],heap.top())){ heap.push(points[i]) if(heap.size>k) heap.pop(); } } // 返回堆中的元素 return heap.arr; }; 复制代码
至此我们就完成了 leetcode-973-最接近原点的 K 个点
如有任何问题或建议，欢迎留言讨论！
