Verwenden Sie die Prioritätswarteschlange, um die K Punkte zu finden, die dem Ursprung am nächsten liegen

In diesem Problem werden wir aus den gegebenen N Punkten die K Punkte finden, die dem Ursprung in der 2D-Ebene am nächsten liegen.

Wir können die standardmäßige euklidische Distanzformel verwenden, um die Distanz zwischen dem Ursprung und jedem gegebenen Punkt zu berechnen. Danach können wir die distanzierten Punkte in einem Array speichern, das Array nach der Entfernung sortieren und die obersten K Punkte nehmen.

Wir können jedoch auch eine Prioritätswarteschlange verwenden, um 2D-Punkte basierend auf ihrer Entfernung vom Ursprung zu speichern. Anschließend können wir K-mal aus der Warteschlange aussteigen.

Problemstellung− Wir erhalten N Punkte auf einer zweidimensionalen Ebene. Wir müssen die K Punkte finden, die dem Ursprung der Ebene am nächsten liegen.

HINWEIS – Stellen Sie sich den euklidischen Abstand als den Abstand zwischen dem Ursprung und einem bestimmten Punkt auf der Ebene vor.

Beispiel

Eintreten

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

Ausgabe

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

Erklärung − Hier ist der euklidische Abstand jedes Punktes zum Ursprung.

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

Die 4 nächstgelegenen Punkte sind also {2,1} {2,−2} {0,3} {−5,1}.

Eintreten

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

Ausgabe

{1, 2}, {2, 1}

Erklärung − Der Abstand aller Punkte zum Ursprung ist gleich. Daher können wir zwei beliebige Punkte als Ausgabe drucken.

Eintreten

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

Ausgabe

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

Erläuterung− K ist gleich dem angegebenen Punkt. Daher müssen wir alle Punkte ausdrucken.

Methode 1

In dieser Methode sortieren wir das Array mit der Methode sort(). Zusätzlich verwenden wir eine Komparatorfunktion, um die Punkte nach ihrer Entfernung vom Ursprung zu sortieren. Danach drucken wir die ersten K Elemente des sortierten Arrays.

Algorithmus

Schritt 1 − Sortieren Sie die Liste mit der Methode sort() und übergeben Sie die Funktion distComparator() als dritten Parameter.

Schritt 2− Definieren Sie die Funktion distComparator(), um die Entfernung eines bestimmten Punktes zu vergleichen. Diese Funktion benötigt als Parameter ein Paar aus p und q.

Schritt 2.1 − Ermitteln Sie den Abstand vom Punkt p zum Ursprung und speichern Sie ihn in dist_p.

Schritt 2.2 − Speichern Sie den Abstand vom Punkt q zum Ursprung in der Variablen dist_q.

Schritt 2.3 − Wenn dist_p kleiner als dist_q ist, gebe true zurück. Andernfalls wird false zurückgegeben.

Schritt 3 – Durchlaufen Sie das Array und drucken Sie die ersten K Punkte des Arrays.

Beispiel

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

Ausgabe

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

Zeitkomplexität – Die Zeitkomplexität beim Sortieren eines Arrays beträgt O(NlogN).

Raumkomplexität – O(N) zum Sortieren eines Arrays.

Methode 2

Bei dieser Methode verwenden wir die Prioritätswarteschlange, um Punkte einzufügen. Darüber hinaus verwenden wir eine Komparatorfunktion und eine Prioritätswarteschlange, um Punkte basierend auf ihrer kürzesten Entfernung vom Ursprung zu speichern.

Algorithmus

Schritt 1 − Definieren Sie die Liste „res_points“, um die K nächstgelegenen Punkte zu speichern.

Schritt 2 – Prioritätswarteschlange definieren. „Paar“ bedeutet hier die Verwendung einer Prioritätswarteschlange zum Speichern von Ganzzahlpaaren. „vector>“ bedeutet die Verwendung von Vektoren zum Speichern von Paaren. Zusätzlich haben wir die Funktion „cmp“ mit einer Prioritätswarteschlange verwendet.

Schritt 3− Definieren Sie die Funktion cmp(), um den euklidischen Abstand zweier Punkte zum Ursprung zu vergleichen.

Schritt 3.1 - Geben Sie einen booleschen Wert zurück, der darauf basiert, dass der Abstand von Punkt a zum Ursprung größer ist als der Abstand von Punkt b zum Ursprung.

Schritt 4- Fügen Sie jedes Element des Arrays in die Prioritätswarteschlange ein.

Schritt 5− Nehmen Sie die ersten K Elemente aus der Warteschlange und speichern Sie sie in der res_points-Liste.

Schritt 6− Geben Sie die res_points-Punkteliste zurück.

Beispiel

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

Ausgabe

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

Zeitkomplexität – O(N*logN) Einfügen von N Elementen in die Prioritätswarteschlange. Dabei ist N die Gesamtpunktzahl.

Raumkomplexität – O(N) zum Speichern von Punkten in der Prioritätswarteschlange.

Prioritätswarteschlange verwendet Heap-Datenstruktur. Daher dauert das Einfügen und Löschen von Elementen nur O(logN) Zeit. Beide Methoden benötigen den gleichen Speicher und die gleiche Zeit. Die zweite Methode ist jedoch effizienter, da sie die Heap-Datenstruktur verwendet.

Das obige ist der detaillierte Inhalt vonVerwenden Sie die Prioritätswarteschlange, um die K Punkte zu finden, die dem Ursprung am nächsten liegen. Für weitere Informationen folgen Sie bitte anderen verwandten Artikeln auf der PHP chinesischen Website!