使用優先隊列找到離原點最近的K個點

在這個問題中，我們將從給定的 N 個點中找到 2D 平面中距離原點最近的 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}

Explanation − 這裡是每個點到原點的歐幾里德距離。

• (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}

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

輸入

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

輸出

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

解釋− K 等於給定點。因此，我們需要列印所有點。

方法一

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

演算法

步驟 1 − 使用sort()方法對清單進行排序，並將distComparator()函數作為第三個參數傳遞。

第二步− 定義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) 用於對陣列進行排序。

方法二

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

演算法

步驟 1 − 定義‘res_points’列表，用於儲存K個最近的點。

步驟 2- 定義優先權佇列。這裡，‘pair’表示使用優先權佇列來儲存整數對。 ‘vector>’表示使用向量來儲存對。此外，我們還使用了具有優先權佇列的“cmp”函數。

第三步驟− 定義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}

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

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

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

以上是使用優先隊列找到離原點最近的K個點的詳細內容。更多資訊請關注PHP中文網其他相關文章！