leecode题解|「leetcode」973. 最接近原点的 K 个点【优先级队列】详解算法|c++|数据结构|队列

本文 https://github.com/youngyangyang04/leetcode-master 已经收录，里面还有leetcode刷题攻略、各个类型经典题目刷题顺序、思维导图，可以fork到自己仓库，有空看一看一定会有所收获，如果对你有帮助也给一个star支持一下吧！

思路这道题其实我在讲解队列的时候，就已经讲过了，在栈与队列：求前 K 个高频元素和队列有啥关系？中，我介绍了一种队列，优先级队列，其实就是大（小）顶堆。
大家有精力的话也可以做做347.前 K 个高频元素，347是求前k的高频元素，本题呢，其实是求前k的低频元素。
所以套路都是一样一样的。
有的同学会用快排，其实快排的话把所有元素都排序了，时间复杂度是O(nlogn)，而使用优先级队列时间复杂度为O(nlogk)，因为只需要维护k个元素有序。
C++代码如下：

class Solution {public: // 大顶堆比较函数 class mycomparison { public: bool operator()(const pair>& lhs, const pair>& rhs) { return lhs.first < rhs.first; } }; vector> kClosest(vector>& points, int K) { // 定义一个大顶堆 priority_queue>, vector>>, mycomparison> pri_que; for(int i = 0; i < points.size(); i++) { int x = points[i][0]; int y = points[i][1]; pair> p(x * x + y * y, points[i]); // key:距离，value是(x,y) pri_que.push(p); if (pri_que.size() > K) { // 如果队列的大小大于了K，则队列弹出，保证队列的大小一直为k pri_que.pop(); } } vector> result(K); // 把队列里元素放入数组 for (int i = 0; i < K; i++) { result[i] = pri_que.top().second; pri_que.pop(); } return result; } };

【leecode题解|「leetcode」973. 最接近原点的 K 个点【优先级队列】详解】我是程序员Carl，利用工作之余重刷leetcode，更多精彩算法文章尽在：代码随想录，关注后，回复「Java」「C++」「python」「简历模板」等等，有我整理多年的学习资料，可以加我微信，备注「简单自我介绍」+「组队刷题」，拉你进入刷题群，每天一道经典题目分析，我选的每一道题目都不是孤立的，而是由浅入深一脉相承的，如果跟住节奏每篇连续着看，定会融会贯通。