Dada una lista de n puntos en un plano 2D, la tarea es encontrar los K (k < n) puntos más cercanos al origen O(0, 0).
Nota: La distancia entre un punto P(x, y) y O(0, 0) utilizando la distancia euclidiana estándar .
Ejemplos:
Entrada: [(1, 0), (2, 1), (3, 6), (-5, 2), (1, -4)], K = 3
Salida: [(1, 0), (2 , 1), (1, -4)]
Explicación: El
cuadrado de las distancias de los puntos desde el origen son
(1, 0) : 1
(2, 1) : 5
(3, 6) : 45
(-5, 2) : 29
(1, -4): 17
Por lo tanto, para K = 3, los 3 puntos más cercanos son (1, 0), (2, 1) y (1, -4).
Entrada: [(1, 3), (-2, 2)], K = 1
Salida: [(-2, 2)]
Explicación:
El cuadrado de las distancias de los puntos desde el origen son
(1, 3) : 10
(-2 , 2) : 8
Por lo tanto, para K = 1, el punto más cercano es (-2, 2).
Enfoque mediante clasificación basada en la distancia: este enfoque se explica en este artículo .
Aproximación usando cola de prioridad para comparación: Para resolver el problema mencionado anteriormente, la idea principal es almacenar las coordenadas del punto en una cola de prioridad de pares, de acuerdo con la distancia del punto desde el origen. Para asignar la máxima prioridad al punto menos distante del origen, usamos la clase Comparator en Priority Queue . Luego imprima los primeros K elementos de la cola de prioridad.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ implementation to find the K
// closest points to origin
// using Priority Queue
#include <bits/stdc++.h>
using namespace std;
// Comparator class to assign
// priority to coordinates
class comp {
public:
bool operator()(pair<int, int> a,
pair<int, int> b)
{
int x1 = a.first * a.first;
int y1 = a.second * a.second;
int x2 = b.first * b.first;
int y2 = b.second * b.second;
// return true if distance
// of point 1 from origin
// is greater than distance of
// point 2 from origin
return (x1 + y1) > (x2 + y2);
}
};
// Function to find the K closest points
void kClosestPoints(int x[], int y[],
int n, int k)
{
// Create a priority queue
priority_queue<pair<int, int>,
vector<pair<int, int> >,
comp>
pq;
// Pushing all the points
// in the queue
for (int i = 0; i < n; i++) {
pq.push(make_pair(x[i], y[i]));
}
// Print the first K elements
// of the queue
for (int i = 0; i < k; i++) {
// Store the top of the queue
// in a temporary pair
pair<int, int> p = pq.top();
// Print the first (x)
// and second (y) of pair
cout << p.first << " "
<< p.second << endl;
// Remove top element
// of priority queue
pq.pop();
}
}
// Driver code
int main()
{
// x coordinate of points
int x[] = { 1, -2 };
// y coordinate of points
int y[] = { 3, 2 };
int K = 1;
int n = sizeof(x) / sizeof(x[0]);
kClosestPoints(x, y, n, K);
return 0;
}
Java
// Java implementation to find the K
// closest points to origin
// using Priority Queue
import java.util.*;
// Point class to store
// a point
class Pair implements Comparable<Pair>
{
int first, second;
Pair(int a, int b)
{
first = a;
second = b;
}
public int compareTo(Pair o)
{
int x1 = first * first;
int y1 = second * second;
int x2 = o.first * o.first;
int y2 = o.second * o.second;
return (x1 + y1) - (x2 + y2);
}
}
class GFG{
// Function to find the K closest points
static void kClosestPoints(int x[], int y[],
int n, int k)
{
// Create a priority queue
PriorityQueue<Pair> pq = new PriorityQueue<>();
// Pushing all the points
// in the queue
for(int i = 0; i < n; i++)
{
pq.add(new Pair(x[i], y[i]));
}
// Print the first K elements
// of the queue
for(int i = 0; i < k; i++)
{
// Remove the top of the queue
// and store in a temporary pair
Pair p = pq.poll();
// Print the first (x)
// and second (y) of pair
System.out.println(p.first +
" " + p.second);
}
}
// Driver code
public static void main(String[] args)
{
// x coordinate of points
int x[] = { 1, -2 };
// y coordinate of points
int y[] = { 3, 2 };
int K = 1;
int n = x.length;
kClosestPoints(x, y, n, K);
}
}
// This code is contributed by jrishabh99
Javascript
<script>
// Javascript implementation to find the K
// closest points to origin
// using Priority Queue
// Function to find the K closest points
function kClosestPoints(x, y, n, k)
{
// Create a priority queue
var pq = [];
// Pushing all the points
// in the queue
for (var i = 0; i < n; i++) {
pq.push([x[i], y[i]]);
}
// Print the first K elements
// of the queue
for (var i = 0; i < k; i++) {
// Store the top of the queue
// in a temporary pair
var p = pq[pq.length-1];
// Print the first (x)
// and second (y) of pair
document.write( p[0] + " "
+ p[1] + "<br>");
// Remove top element
// of priority queue
pq.pop();
}
}
// Driver code
// x coordinate of points
var x = [1, -2];
// y coordinate of points
var y = [3, 2];
var K = 1;
var n = x.length;
kClosestPoints(x, y, n, K);
// This code is contributed by rutvik_56.
</script>
Python3
# Python3 implementation to find the K
# closest points to origin
# using Priority Queue
import heapq as hq
# Function to find the K closest points
def kClosestPoints(x, y, n, k):
# Create a priority queue
pq=[]
# Pushing all the points
# in the queue
for i in range(n):
hq.heappush(pq, (x[i]*x[i]+y[i]*y[i],x[i],y[i]))
# Print the first K elements
# of the queue
for i in range(k) :
# Store the top of the queue
# in a temporary pair
p = hq.heappop(pq)
# Print the first (x)
# and second (y) of pair
print("{} {}".format(p[1],p[2]))
# Driver code
if __name__ == '__main__':
# x coordinate of points
x = [1, -2]
# y coordinate of points
y = [3, 2]
K = 1
n=len(x)
kClosestPoints(x, y, n, K)
-2 2
Complejidad de tiempo: O(N + K * log(N))
Espacio auxiliar : O(N)