使用優先佇列查詢距離原點最近的 K 個點

---

在這個問題中，我們將從給定的 N 個點中找到二維平面中距離原點最近的 K 個點。

我們可以使用標準的歐幾里得距離公式來計算原點與每個給定點之間的距離。之後，我們可以將點與距離儲存在陣列中，根據距離對陣列進行排序，並取前 K 個點。

但是，我們也可以使用優先佇列根據點到原點的距離來儲存二維點。之後，我們可以對佇列進行 K 次出隊操作。

問題陳述 - 我們在二維平面上給出了 N 個點。我們需要找到平面中距離原點最近的 K 個點。

注意 - 將歐幾里得距離視為原點與平面給定點之間的距離。

示例

輸入

points = {{2, -2}, {-5, 1}, {2, 1}, {0, 3}, {6, 0}, {5, 5}, {4, 9}}, K = 4

輸出

{2,1} {2,-2} {0,3} {-5,1}

說明 - 以下是每個點到原點的歐幾里得距離。

• (2, −2) −> sqrt(8)

• (−5, 1) −> sqrt(26)

• (2, 1) −> sqrt(5)

• (0, 3) −> sqrt(9)

• (6, 0) −> sqrt(36)

• (5, 5) −> sqrt(50)

• (4, 9) −> sqrt(97)

因此，4 個最近的點是 {2,1} {2,−2} {0,3} {−5,1}。

輸入

points = {{1, 2}, {2, 1}, {-2, 1}, {1, -2}} K = 2

輸出

{1, 2}, {2, 1}

說明 - 所有點到原點的距離都相同。因此，我們可以列印任意 2 個點作為輸出。

輸入

points = {{1, 3}, {6, 7}, {1, 1}, {1, 0}} K = 4

輸出

{1, 0}, {1, 1}, {1, 3}, {6, 7}

說明 - K 等於給定點。因此，我們需要列印所有點。

方法 1

在這種方法中，我們將使用 sort() 方法對陣列進行排序。此外，我們將使用比較器函式根據點到原點的距離對點進行排序。之後，我們列印排序陣列的前 K 個元素。

演算法

步驟 1 - 使用 sort() 方法對列表進行排序，並將 distComparator() 函式作為第三個引數傳遞。

步驟 2 - 定義 distComparator() 函式來比較給定點的距離。該函式將 p 和 q 對作為引數。

步驟 2.1 - 獲取點 p 到原點的距離並將其儲存在 dist_p 中。

步驟 2.2 - 獲取點 q 到原點的距離並將其儲存在 dist_q 變數中。

步驟 2.3 - 如果 dist_p 小於 dist_q，則返回 true。否則，返回 false。

步驟 3 - 遍歷陣列，並列印陣列的前 K 個點。

示例

#include <bits/stdc++.h>
using namespace std;

bool distComparator(const pair<int, int> &p, const pair<int, int> &q) {
    int dist_p = p.first * p.first + p.second * p.second;
    int dist_q = q.first * q.first + q.second * q.second;
    return dist_p < dist_q;
}
vector<pair<int, int>> findKPoints(vector<pair<int, int>> points, int n, int k) {
    vector<pair<int, int>> res_points;
    sort(points.begin(), points.end(), distComparator);
    // Get the first K points
    for (int p = 0; p < k; p++)     {
        res_points.push_back({points[p].first, points[p].second});
    }
    return res_points;
}
int main() {
    int k = 4, n = 7;
    vector<pair<int, int>> points{{2, -2}, {-5, 1}, {2, 1}, {0, 3}, {6, 0}, {5, 5}, {4, 9}};
    vector<pair<int, int>> res = findKPoints(points, n, k);
    cout << "The " << k << " closest points from origin are - ";
    for (int p = 0; p < k; p++) {
        cout << "{" << res[p].first << "," << res[p].second << "} ";
    }
    return 0;
}

輸出

The 4 closest points from origin are - {2,1} {2,-2} {0,3} {-5,1}

時間複雜度 - 對陣列進行排序的 O(NlogN)。

空間複雜度 - 對陣列進行排序的 O(N)。

方法 2

在這種方法中，我們將使用優先佇列插入點。此外，我們將使用比較器函式和優先佇列根據點到原點的最短距離來儲存點。

演算法

步驟 1 - 定義 ‘res_points’ 點對列表以儲存 K 個最近的點。

步驟 2 - 定義優先佇列。這裡，‘pair<int, int>’ 表示使用優先佇列儲存整數對。‘vector<pair<int, int>>’ 表示使用向量儲存對。此外，我們使用了 ‘cmp’ 函式與優先佇列。

步驟 3 - 定義 cmp() 函式來比較兩個點到原點的歐幾里得距離。

步驟 3.1 - 根據點 a 的距離大於點 b 到原點的距離返回布林值。

步驟 4 - 將陣列的每個元素插入優先佇列。

步驟 5 - 從佇列中彈出前 K 個元素並將它們儲存到 res_points 列表中。

步驟 6 - 返回 res_points 點列表。

示例

#include <bits/stdc++.h>
using namespace std;

vector<pair<int, int>> findKPoints(vector<pair<int, int>> points, int n, int k) {
    vector<pair<int, int>> res_points;
    // Custom comparator to compare points based on their distance from the origin
    auto cmp = [](const pair<int, int>& a, const pair<int, int>& b) {
        return (a.first * a.first + a.second * a.second) > (b.first * b.first + b.second * b.second);
    };
    // Use the custom comparator in the priority_queue
    priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> p_que(cmp);
    for (int p = 0; p < n; p++) {
        // Inserting points in a queue
        p_que.push(points[p]);
    }
    // Get first K points
    while (k--) {
        auto temp = p_que.top();
        res_points.push_back(temp);
        p_que.pop();
    }
    return res_points;
}
int main() {
    int k = 4, n = 7;
    vector<pair<int, int>> points{{2, -2}, {-5, 1}, {2, 1}, {0, 3}, {6, 0}, {5, 5}, {4, 9}};
    vector<pair<int, int>> res = findKPoints(points, n, k);
    cout << "The " << k << " closest points from origin are - ";
    for (int p = 0; p < k; p++) {
        cout << "{" << res[p].first << "," << res[p].second << "} ";
    }
    return 0;
}

輸出

The 4 closest points from origin are - {2,1} {2,-2} {0,3} {-5,1}

時間複雜度 - 將 N 個元素插入優先佇列的 O(N*logN)。這裡，N 是點的總數。

空間複雜度 - 在優先佇列中儲存點的 O(N)。

優先佇列使用堆資料結構。因此，插入和刪除元素只需要 O(logN) 時間。兩種方法都佔用相同記憶體和時間。但是，第二種方法更有效，因為它使用堆資料結構。