LeetCode 973. 最接近原點的 K 個點 C++代碼——Leetcode刷題筆記+思路分享

LeetCode 973. 最接近原點的 K 個點

本文總結了兩個方法：

• 方法一為本人所使用的直接排序方法，簡單易實作；
• 方法二使用了優先隊列這一資料結構，耗時更短。

方法一：排序

重寫

cmp()

函數，使用

sort()

進行直接排序。

代碼

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

方法二：優先隊列

優先隊列具有隊列的所有特性，包括基本操作，隻是在這基礎上添加了内部的一個排序，它本質是一個堆實作的，它和queue不同的就在于我們可以自定義其中資料的優先級, 讓優先級高的排在隊列前面,優先出隊。

而對于

pair

的隊列，會先比較第一個元素，若第一個相等再比較第二個。

使用一個優先隊列（大根堆）實時維護前 K 個最小的距離平方。

将前 K 個點的距離平方以及對應的編号（為了友善最後直接得到答案）放入優先隊列中。

随後從第 K+1 個點開始周遊：如果目前點的距離平方比堆頂的點的距離平方要小，就把堆頂（因為是大根堆）的點彈出，再插入目前的點。

當周遊完成後，所有在優先隊列中的點就是前 K 個距離最小的點。

不同的語言提供的優先隊列的預設情況不一定相同。在 C++ 語言中，優先隊列預設為大根堆。

代碼

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < K; ++i) {
            q.emplace(points[i][0] * points[i][0] + points[i][1] * points[i][1], i);
        }
        int n = points.size();
        for (int i = K; i < n; ++i) {
            int dist = points[i][0] * points[i][0] + points[i][1] * points[i][1];
            if (dist < q.top().first) {
                q.pop();
                q.emplace(dist, i);
            }
        }
        vector<vector<int>> ans;
        while (!q.empty()) {
            ans.push_back(points[q.top().second]);
            q.pop();
        }
        return ans;
    }
};
           

原題傳送門