Dada una lista de puntos en el plano 2-D arr[][] , un punto target dado y un entero K . La tarea es encontrar los puntos K más cercanos al objetivo de la lista de puntos dada.
Nota: La distancia entre dos puntos en un plano es la distancia euclidiana .
Ejemplos:
Entrada: puntos = [[3, 3], [5, -1], [-2, 4]], objetivo = [0, 0], K = 2 Salida: [[3, 3], [
-2 , 4]]
Explicación: El cuadrado de la distancia del objetivo (=origen) desde este punto es
(3, 3) = 18
(5, -1) = 26
(-2, 4) = 20
Entonces los dos puntos más cercanos son [3, 3], [-2, 4].Entrada: puntos = [[1, 3], [-2, 2]], objetivo = [0, 1], K = 1
Salida: [[1, 3]]
Enfoque: La solución se basa en el enfoque Greedy . La idea es calcular la distancia euclidiana desde el objetivo para cada punto dado y almacenarlos en una array. Luego ordene la array de acuerdo con la distancia euclidiana encontrada e imprima los primeros k puntos más cercanos de la lista.
A continuación se muestra la implementación del enfoque anterior.
C++
// C++ program to implement of above approach
#include <bits/stdc++.h>
using namespace std;
// Calculate the Euclidean distance
// between two points
float distance(int x1, int y1, int x2, int y2)
{
return sqrt(pow((x1 - x2), 2) +
pow((y1 - y2), 2));
}
// Function to calculate K closest points
vector<vector<int> > kClosest(
vector<vector<int> >& points,
vector<int> target, int K)
{
vector<vector<int> > pts;
int n = points.size();
vector<pair<float, int> > d;
for (int i = 0; i < n; i++) {
d.push_back(
make_pair(distance(points[i][0], points[i][1],
target[0], target[1]),
i));
}
sort(d.begin(), d.end());
for (int i = 0; i < K; i++) {
vector<int> pt;
pt.push_back(points[d[i].second][0]);
pt.push_back(points[d[i].second][1]);
pts.push_back(pt);
}
return pts;
}
// Driver code
int main()
{
vector<vector<int> > points
= { { 1, 3 }, { -2, 2 } };
vector<int> target = { 0, 1 };
int K = 1;
for (auto pt : kClosest(points, target, K)) {
cout << pt[0] << " " << pt[1] << endl;
}
return 0;
}
Java
// Java program to implement of above approach
import java.util.*;
class GFG{
static class pair
{
float first;
float second;
public pair(float f, float second)
{
this.first = f;
this.second = second;
}
}
// Calculate the Euclidean distance
// between two points
static float distance(int x1, int y1, int x2, int y2)
{
return (float) Math.sqrt(Math.pow((x1 - x2), 2) +
Math.pow((y1 - y2), 2));
}
// Function to calculate K closest points
static Vector<Vector<Integer> > kClosest(
int[][] points,
int[] target, int K)
{
Vector<Vector<Integer>> pts = new Vector<Vector<Integer>>();
int n = points.length;
Vector<pair> d = new Vector<pair>();
for (int i = 0; i < n; i++) {
d.add(
new pair(distance(points[i][0], points[i][1],
target[0], target[1]),
i));
}
Collections.sort(d, (a, b) -> (int)(a.first - b.first));
for (int i = 0; i < K; i++) {
Vector<Integer> pt = new Vector<Integer>();
pt.add(points[(int) d.get(i).second][0]);
pt.add(points[(int) d.get(i).second][1]);
pts.add(pt);
}
return pts;
}
// Driver code
public static void main(String[] args)
{
int[][] points
= { { 1, 3 }, { -2, 2 } };
int[] target = { 0, 1 };
int K = 1;
for (Vector<Integer> pt : kClosest(points, target, K)) {
System.out.print(pt.get(0)+ " " + pt.get(1) +"\n");
}
}
}
// This code is contributed by 29AjayKumar
Python3
# Python code for the above approach
# Calculate the Euclidean distance
# between two points
def distance(x1, y1, x2, y2):
return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** ( 1 / 2)
# Function to calculate K closest points
def kClosest(points, target, K):
pts = []
n = len(points)
d = []
for i in range(n):
d.append({
"first": distance(points[i][0], points[i][1], target[0], target[1]),
"second": i
})
d = sorted(d, key=lambda l:l["first"])
for i in range(K):
pt = []
pt.append(points[d[i]["second"]][0])
pt.append(points[d[i]["second"]][1])
pts.append(pt)
return pts
# Driver code
points = [[1, 3], [-2, 2]]
target = [0, 1]
K = 1
for pt in kClosest(points, target, K):
print(f"{pt[0]} {pt[1]}")
# This code is contributed by gfgking.
C#
// C# program to implement of above approach
using System;
using System.Collections.Generic;
public class GFG {
public class pair {
public float first;
public float second;
public pair(float f, float second) {
this.first = f;
this.second = second;
}
}
// Calculate the Euclidean distance
// between two points
static float distance(int x1, int y1,
int x2, int y2)
{
return (float) Math.Sqrt(Math.Pow((x1 - x2), 2) +
Math.Pow((y1 - y2), 2));
}
// Function to calculate K closest points
static List<List<int>> kClosest(int[,] points,
int[] target, int K)
{
List<List<int>> pts = new List<List<int>>();
int n = points.GetLength(0);
List<pair> d = new List<pair>();
for (int i = 0; i < n; i++) {
d.Add(new pair(distance(points[i,0], points[i,1],
target[0], target[1]), i));
}
for (int i = 0; i < K; i++) {
List<int> pt = new List<int>();
pt.Add(points[(int) d[i].second,0]);
pt.Add(points[(int) d[i].second,1]);
pts.Add(pt);
}
return pts;
}
// Driver code
public static void Main(String[] args) {
int[,] points = { { 1, 3 }, { -2, 2 } };
int[] target = { 0, 1 };
int K = 1;
foreach (List<int> pt in kClosest(points, target, K))
{
Console.Write(pt[0] + " " + pt[1] + "\n");
}
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// JavaScript code for the above approach
// Calculate the Euclidean distance
// between two points
function distance(x1, y1, x2, y2)
{
return Math.sqrt(Math.pow((x1 - x2), 2) +
Math.pow((y1 - y2), 2));
}
// Function to calculate K closest points
function kClosest(points,
target, K)
{
let pts = [];
let n = points.length;
let d = [];
for (let i = 0; i < n; i++) {
d.push({
first: distance(points[i][0], points[i][1],
target[0], target[1]), second: i
});
}
d.sort(function (a, b) { return a.first < b.first })
for (let i = 0; i < K; i++) {
let pt = [];
pt.push(points[d[i].second][0]);
pt.push(points[d[i].second][1]);
pts.push(pt);
}
return pts;
}
// Driver code
let points
= [[1, 3], [-2, 2]];
let target = [0, 1];
let K = 1;
for (let pt of kClosest(points, target, K)) {
document.write(pt[0] + " " + pt[1] + '<br>');
}
// This code is contributed by Potta Lokesh
</script>
Producción
1 3
Complejidad temporal: O(N * logN)
Espacio auxiliar: O(N)