Gunakan baris gilir keutamaan untuk mencari K titik yang paling hampir dengan asal

Dalam masalah ini, kita akan mencari titik K yang paling hampir dengan asalan dalam satah 2D dari titik N yang diberikan.

Kita boleh menggunakan formula jarak Euclidean standard untuk mengira jarak dari asal ke setiap titik yang diberikan. Selepas itu, kita boleh menyimpan titik jarak ke dalam tatasusunan, menyusun tatasusunan berdasarkan jarak, dan mengambil mata K teratas.

Namun, kami juga boleh menggunakan baris gilir keutamaan untuk menyimpan mata 2D berdasarkan jaraknya dari asal. Selepas itu, kita boleh dequeue K kali daripada queue.

Pernyataan Masalah− Kami diberi N mata pada satah dua dimensi. Kita perlu mencari titik K yang paling hampir dengan asal kapal terbang.

NOTA- Fikirkan jarak Euclidean sebagai jarak antara asalan dan titik tertentu pada satah.

Contoh

Masuk

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

Output

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

Penjelasan − Berikut ialah jarak Euclidean bagi setiap titik ke asal.

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

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

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

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

• (6, 0) -> persegi(36)

• (5, 5) -> persegi(50)

• (4, 9) -> persegi(97)

Oleh itu, 4 titik terdekat ialah {2,1} {2,−2} {0,3} {−5,1}.

Masuk

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

Output

{1, 2}, {2, 1}

Penjelasan − Jarak dari semua titik ke asal adalah sama. Oleh itu, kita boleh mencetak mana-mana 2 mata sebagai output.

Masuk

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

Output

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

Penjelasan− K adalah sama dengan titik yang diberikan. Oleh itu, kita perlu mencetak semua mata.

Kaedah 1

Dalam kaedah ini kita akan mengisih tatasusunan menggunakan kaedah sort(). Selain itu, kami akan menggunakan fungsi pembanding untuk mengisih titik berdasarkan jaraknya dari asal. Selepas itu, kami mencetak elemen K pertama tatasusunan yang diisih.

Algoritma

Langkah 1 − Isih senarai menggunakan kaedah sort() dan lulus fungsi distComparator() sebagai parameter ketiga.

Langkah 2− Tentukan fungsi distComparator() untuk membandingkan jarak titik tertentu. Fungsi ini mengambil sebagai parameter sepasang p dan q.

Langkah 2.1 − Dapatkan jarak dari titik p ke asal dan simpan dalam dist_p.

Langkah 2.2 − Simpan jarak dari titik q ke asal dalam pembolehubah dist_q.

Langkah 2.3 − Jika dist_p kurang daripada dist_q, kembalikan benar. Jika tidak, pulangan palsu.

Langkah 3- Gelung melalui tatasusunan dan cetak titik K pertama tatasusunan.

Contoh

#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;
}

Output

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

Kerumitan Masa - Kerumitan masa untuk menyusun tatasusunan ialah O(NlogN).

Kerumitan Ruang - O(N) untuk mengisih tatasusunan.

Kaedah 2

Dalam kaedah ini kita akan menggunakan baris gilir keutamaan untuk memasukkan mata. Selain itu, kami akan menggunakan fungsi pembanding dan baris gilir keutamaan untuk menyimpan mata berdasarkan jarak terpendeknya dari asal.

Algoritma

Langkah 1 − Tentukan senarai 'res_points' untuk menyimpan K mata terdekat.

Langkah 2- Tentukan baris gilir keutamaan. Di sini, 'pasangan' bermaksud menggunakan baris gilir keutamaan untuk menyimpan pasangan integer. ‘vector>’ bermaksud menggunakan vektor untuk menyimpan pasangan. Selain itu, kami menggunakan fungsi "cmp" dengan baris gilir keutamaan.

Langkah 3− Takrifkan fungsi cmp() untuk membandingkan jarak Euclidean dua titik dengan asalan.

Langkah 3.1 - Kembalikan nilai Boolean berdasarkan jarak dari titik a ke asal yang lebih besar daripada jarak dari titik b ke asal.

Langkah 4- Masukkan setiap elemen tatasusunan ke dalam baris gilir keutamaan.

Langkah 5− Pop elemen K pertama daripada baris gilir dan simpannya dalam senarai res_points.

Langkah 6− Kembalikan senarai mata_res_mata.

Contoh

#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;
}

Output

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

Kerumitan masa - O(N*logN) Memasukkan elemen N ke dalam baris gilir keutamaan. Di sini, N ialah jumlah bilangan mata.

Kerumitan Ruang - O(N) untuk menyimpan mata dalam baris gilir keutamaan.

Baris gilir keutamaan menggunakan struktur data timbunan. Oleh itu, memasukkan dan memadam elemen hanya mengambil masa O(logN). Kedua-dua kaedah memerlukan memori dan masa yang sama. Walau bagaimanapun, kaedah kedua adalah lebih cekap kerana ia menggunakan struktur data timbunan.

Atas ialah kandungan terperinci Gunakan baris gilir keutamaan untuk mencari K titik yang paling hampir dengan asal. Untuk maklumat lanjut, sila ikut artikel berkaitan lain di laman web China PHP!