leetcode 973. K Closest Points to Origin [Medium]

2021-12-26 173 words One minute

Contents

題目敘述

給 n 個座標，返回距離原點最近的 k 個座標

解題紀錄

解法一

因為要返回的只有座標點，所以其實不需要開根號，直接用 (x^2 + y^2) 比較即可。

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        sort(points.begin(), points.end(), [this](vector<int> &a, vector<int> &b) {
            return get_distance(a) < get_distance(b);
        });
        
        return vector<vector<int>>(points.begin(), points.begin() + k);
    }
    
    inline int get_distance(vector<int> &point) {
        return point[0] * point[0] + point[1] * point[1];
    }
};

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
static auto _ = [] () {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

解法二

求最近的 k 個節點，其實可以換個思路，利用 maxHeap 來實現。

每次計算距離之後連同座標 push 進 maxHeap，因為要維持前 k 個，所以如果 maxHeap 內的元素多餘 k 個時，就利用 maxHeap 的特性，把裡面最大的元素 pop 出來。

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        vector<vector<int>> solution;
        
        priority_queue<vector<int>> maxHeap;
        
        for (auto& point: points) {
            maxHeap.push({get_distance(point), point[0], point[1]});
            
            if (maxHeap.size() > k) {
                maxHeap.pop();
            }
        }
        
        for (int i = 0; i < k; ++i) {
            auto p = maxHeap.top();
            maxHeap.pop();
            solution.push_back({p[1], p[2]});
        }
        return solution;
    }
    inline int get_distance(vector<int> &point) {
        return point[0] * point[0] + point[1] * point[1];
    }
};

#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
static auto _ = [] () {ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);return 0;}();

解法三 QuickSelect

待補，最佳解