Utilisez la file d'attente prioritaire pour trouver les K points les plus proches de l'origine

Dans ce problème, nous trouverons les K points les plus proches de l'origine dans le plan 2D à partir des N points donnés.

Nous pouvons utiliser la formule de distance euclidienne standard pour calculer la distance entre l'origine et chaque point donné. Après cela, nous pouvons stocker les points avec distance dans un tableau, trier le tableau en fonction de la distance et prendre les K premiers points.

Cependant, nous pouvons également utiliser une file d'attente prioritaire pour stocker les points 2D en fonction de leur distance par rapport à l'origine. Ensuite, nous pouvons retirer K fois de la file d’attente.

Énoncé du problème− On nous donne N points sur un plan bidimensionnel. Nous devons trouver les points K les plus proches de l’origine du plan.

REMARQUE- Considérez la distance euclidienne comme la distance entre l'origine et un point donné sur le plan.

Exemple

Entrez

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

Sortie

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

Explication − Voici la distance euclidienne de chaque point à l'origine.

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

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

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

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

• (6, 0) -> carré(36)

• (5, 5) -> carré(50)

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

Ainsi, les 4 points les plus proches sont {2,1} {2,−2} {0,3} {−5,1}.

Entrez

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

Sortie

{1, 2}, {2, 1}

Explication − La distance de tous les points à l'origine est la même. Par conséquent, nous pouvons imprimer 2 points en sortie.

Entrez

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

Sortie

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

Explication− K est égal au point donné. Par conséquent, nous devons imprimer tous les points.

Méthode 1

Dans cette méthode, nous trierons le tableau à l'aide de la méthode sort(). De plus, nous utiliserons une fonction de comparaison pour trier les points en fonction de leur distance par rapport à l'origine. Après cela, nous imprimons les K premiers éléments du tableau trié.

Algorithme

Étape 1 − Utilisez la méthode sort() pour trier la liste et transmettez la fonction distComparator() comme troisième paramètre.

Étape 2− Définissez la fonction distComparator() pour comparer la distance d'un point donné. Cette fonction prend comme paramètres une paire de p et q.

Étape 2.1 − Obtenez la distance du point p à l'origine et stockez-la dans dist_p.

Étape 2.2 − Stockez la distance du point q à l'origine dans la variable dist_q.

Étape 2.3 − Si dist_p est inférieur à dist_q, retournez vrai. Sinon, renvoie faux.

Étape 3- Parcourez le tableau et imprimez les K premiers points du tableau.

Exemple

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

Sortie

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

Complexité temporelle - La complexité temporelle du tri d'un tableau est O(NlogN).

Complexité spatiale - O(N) pour trier un tableau.

Méthode 2

Dans cette méthode, nous utiliserons la file d'attente prioritaire pour insérer des points. De plus, nous utiliserons une fonction de comparaison et une file d'attente prioritaire pour stocker les points en fonction de leur distance la plus courte depuis l'origine.

Algorithme

Étape 1 − Définissez la liste 'res_points' pour stocker les K points les plus proches.

Étape 2- Définir la file d'attente prioritaire. Ici, « paire » signifie utiliser une file d’attente prioritaire pour stocker des paires entières. « vecteur> » signifie utiliser des vecteurs pour stocker des paires. De plus, nous avons utilisé la fonction "cmp" avec une file d'attente prioritaire.

Étape 3− Définissez la fonction cmp() pour comparer la distance euclidienne de deux points à l'origine.

Étape 3.1 - Renvoie une valeur booléenne basée sur la distance du point a à l'origine étant supérieure à la distance du point b à l'origine.

Étape 4- Insérez chaque élément du tableau dans la file d'attente prioritaire.

Étape 5− Extrayez les K premiers éléments de la file d'attente et stockez-les dans la liste res_points.

Étape 6− Renvoie la liste de points res_points.

Exemple

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

Sortie

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

Complexité temporelle - O(N*logN) Insertion de N éléments dans la file d'attente prioritaire. Ici, N est le nombre total de points.

Complexité spatiale - O(N) pour stocker les points dans la file d'attente prioritaire.

La file d'attente prioritaire utilise une structure de données de tas. Par conséquent, l’insertion et la suppression d’éléments ne prennent que du temps O(logN). Les deux méthodes nécessitent la même mémoire et le même temps. Cependant, la deuxième méthode est plus efficace car elle utilise la structure de données tas.

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!