文章目錄

• • 1. 題目
  • 2. 解題
  • • 2.1 排序
    • 2.2 優先隊列
    • 2.3 快排思路

1. 題目

我們有一個由平面上的點組成的列表 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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/k-closest-points-to-origin
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

2. 解題

類似題目：LeetCode 215. 數組中的第K個最大元素（快速排序）

2.1 排序

class Solution { public:vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {if(K == points.size())return points;sort(points.begin(),points.end(),[&](auto a, auto b){return a[0]*a[0]+a[1]*a[1] < b[0]*b[0]+b[1]*b[1];});points.resize(K);return points;} };

1772 ms 191.6 MB

partial_sort 只對前部分[first,middle)進行排序，前部分實現為堆

class Solution { public:vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {partial_sort(points.begin(), points.begin() + K, points.end(), [&] (auto a, auto b){return a[0]*a[0]+a[1]*a[1] < b[0]*b[0]+b[1]*b[1]; });points.resize(K);return points;} };

1552 ms 148.4 MB
時間復雜度 $O(nlogn)$

2.2 優先隊列

• 維持一個容量為K的大頂堆
• 隊列滿了，后續點比堆頂更接近原點時，pop堆頂，push當前點

struct cmp{bool operator()(const vector<int>& a, const vector<int>& b)const{return a[0]*a[0]+a[1]*a[1] < b[0]*b[0]+b[1]*b[1];//大頂堆} }; class Solution { public:vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {if(K == points.size())return points;priority_queue<vector<int>, vector<vector<int>>, cmp> q;for(int i = 0; i < points.size(); ++i){if(q.size() < K)q.push(points[i]);else if(q.top()[0]*q.top()[0]+q.top()[1]*q.top()[1] > points[i][0]*points[i][0]+points[i][1]*points[i][1]){q.pop();q.push(points[i]);}}vector<vector<int>> ans(q.size());int i = 0;while(!q.empty()){ans[i++] = q.top();q.pop();}return ans;} };

時間復雜度 $O(nlogK)$
628 ms 47.5 MB

2.3 快排思路

class Solution { public:vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {if(K == points.size())return points;findkth(points,0,points.size()-1,K);points.resize(K);return points;}int dis(vector<vector<int>>& points, int i){return points[i][0]*points[i][0]+points[i][1]*points[i][1];}void findkth(vector<vector<int>>& points,int l, int r, int K){int i = l, j = r, p = dis(points, l);while(i < j){while(i < j && dis(points,j) > p)//必須先從右邊開始，因為選的pivot在左邊j--;while(i < j && dis(points,i) <= p)i++;swap(points[i], points[j]);}swap(points[l], points[i]);if(i < K)//左邊都是答案的一部分，取右邊找findkth(points,i+1,r,K);else if(i > K)//左邊多于K個，在左邊繼續分割findkth(points,l,i-1,K);elsereturn;} };

時間復雜度 $O(n)$
244 ms 39 MB

創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎

總結

以上是生活随笔為你收集整理的LeetCode 973. 最接近原点的 K 个点（排序/优先队列/快排）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。