Programando K Closest Points to Origin con Python

Bueno yo me fui a la documentación porque no sabia mucho sobre el modulo heapq y en ella vi la solucion al problema pues los elementos del heap también pueden ser tuplas (prioridad, valor) en este caso mi prioridad es la distancia y mi valor es el punto, sabiendo que el método heappop() devuelve el elemento más pequeño, al usar tuplas se devuelve el par (distancia, punto) con la distancia más pequeña lo que es genial! para resolver el problema en unos pocos pasos 😁, aqui les dejo mi solución

import heapq
import math
from typing import List

def kClosest(puntos: List[List[int]], K: int) -> List[List[int]]:
   heap = []
   for punto in puntos:
      distance = math.sqrt((punto[0]**2) + (punto[1]**2))
      heapq.heappush(heap, (distance, punto))
   
   #print(heapq.heappop(heap))
   
   k_puntos = [heapq.heappop(heap)[1] for _ in range(K)]
   
   return k_puntos

response = kClosest([[1,3], [3,4], [5,6]], 1)
print(response)

response = kClosest([[13,-8], [1,20], [-5,5]], 2)
print(response)

Esta es mi solución en java, utilicé un PriorityQueue ```js public class KClosesPointsToOrigin { public static void main(String[] args) { int[][] points = {{2, 3}, {3, 3}, {1, 2}, {4, 5}}; int k = 2; int[][] closestPoints = findClosestPoints(points, k); for(int[] point : closestPoints){ System.out.printf("[%d, %d] ", point[0], point[1]); } } private static int[][] findClosestPoints(int[][] points, int k) { PriorityQueue<int[]> queue = new PriorityQueue<>(Comparator.comparingInt(a -> (a[0] * a[0] + a[1] * a[1]))); Collections.addAll(queue, points); int[][] result = new int[k][]; for(int i = 0; i

Esta es mi solución en Java:   

Solución en Java

package org.example.points;

import java.util.*;

public class PointsPriorityQueue {

    class CustomComparable implements Comparator<Integer[]> {

        private Integer calculateDistance (Integer point[]) {
            return (point[0]*point[0]) + (point[1]*point[1]);
        }

        @Override
        public int compare(Integer[] p1, Integer[] p2) {
            return calculateDistance(p1).compareTo(calculateDistance(p2));
        }
    }

    PriorityQueue<Integer[]> queue = new PriorityQueue<>(new CustomComparable());

    public void set (List<Integer[]> points) {
        points.forEach(queue::add);
    }

    public List<Integer[]> getTheClosestPoints(int numberOfPoints) {
        if (queue.isEmpty()) return Collections.EMPTY_LIST;

        if (queue.size() == numberOfPoints) {
            return queue.stream().toList();
        }

        List<Integer[]> list = new ArrayList<>();

        int count = 0;
        while (count < numberOfPoints) {
            list.add(queue.poll());
            count++;
        }

        return list;
    }
}

Estos son los tests que escribi para la clase

import org.example.points.PointsPriorityQueue;
import org.junit.jupiter.api.Test;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

import static org.junit.jupiter.api.Assertions.*;

public class PointsPriorityQueueTest {

    @Test
    public void shouldReturnNothingPointBecauseThereIsNotAnyPointIntoQueue () {
        PointsPriorityQueue points = new PointsPriorityQueue();
        assertEquals(Collections.EMPTY_LIST, points.getTheClosestPoints(2));
    }

    private List<Integer[]> mockPoints () {
        List<Integer[]> x = new ArrayList<>();
        x.add(new Integer[]{-10,1});
        x.add(new Integer[]{3,4});
        x.add(new Integer[]{1,3});
        x.add(new Integer[]{-2,7});

        return x;
    }

    private void testEachPoint (Integer[] point, Integer x1, Integer y1) {
        assertEquals(point[0], x1);
        assertEquals(point[1], y1);
    }

    @Test
    public void shouldReturnAllPointsBecauseTheNumberOfPointsIsTheSamePointsStored () {
        PointsPriorityQueue points = new PointsPriorityQueue();

        points.set(mockPoints());
        List<Integer[]> closetPoints = points.getTheClosestPoints(4);

        assertEquals(4, closetPoints.size());

        testEachPoint(closetPoints.get(0), 1, 3);
        testEachPoint(closetPoints.get(1), -2, 7);
    }

    @Test
    public void shouldReturnOneClosetsPoint () {
        PointsPriorityQueue points = new PointsPriorityQueue();

        points.set(mockPoints());
        List<Integer[]> closetPoints = points.getTheClosestPoints(1);

        assertNotNull(closetPoints);
        assertEquals(1, closetPoints.size());

        testEachPoint(closetPoints.get(0), 1, 3);
    }

    @Test
    public void shouldReturnTwoClosetsPoints () {
        PointsPriorityQueue points = new PointsPriorityQueue();

        points.set(mockPoints());
        List<Integer[]> closetPoints = points.getTheClosestPoints(2);

        assertNotNull(closetPoints);
        assertEquals(2, closetPoints.size());

        testEachPoint(closetPoints.get(0), 1, 3);
        testEachPoint(closetPoints.get(1), 3, 4);
    }

    @Test
    public void shouldReturnThreeClosetsPoints () {
        PointsPriorityQueue points = new PointsPriorityQueue();

        points.set(mockPoints());
        List<Integer[]> closetPoints = points.getTheClosestPoints(3);

        assertNotNull(closetPoints);
        assertEquals(3, closetPoints.size());

        testEachPoint(closetPoints.get(0), 1, 3);
        testEachPoint(closetPoints.get(1), 3, 4);
        testEachPoint(closetPoints.get(2), -2, 7);
    }

}

probando el código de la profe. Haciendo pruebas, se entiende mejor:

---

Solucion en c++

#include <iostream>
#include <fstream>
#include <string>
#include <stack>
#include <vector>
#include <cmath>

using namespace std;

int main()
{
    int k = 2;

    fstream archivo;
    vector<pair<int, int>> puntos;
    stack<pair<int, int>> pila;

    archivo.open("puntos.txt", ios::in);

    while (!archivo.eof())
    {
        int x, y;
        string linea;
        getline(archivo, linea);
        x = stoi(linea.substr(0, linea.find(",")));
        y = stoi(linea.substr(linea.find(",") + 1, linea.length()));
        puntos.push_back(make_pair(x, y));
    }

    archivo.close();

    if (k > puntos.size())
    {
        cout << "El valor de k es mayor que la cantidad de puntos" << endl;
        return 0;
    }
    else if (k == puntos.size())
    {
        cout << "Los puntos mas cercanos al origen son: " << endl;
        for (int i = 0; i < puntos.size(); i++)
        {
            cout << puntos[i].first << "," << puntos[i].second << endl;
        }
        return 0;
    }

    for (int i = 0; i < puntos.size(); i++)
    {
        if (pila.size() < k)
        {
            pila.push(puntos[i]);
        }
        else
        {

            double distance_current = sqrt(puntos[i].first * puntos[i].first + puntos[i].second * puntos[i].second);

            double distance_top = sqrt(pila.top().first * pila.top().first + pila.top().second * pila.top().second);

            if (distance_current < distance_top)
            {
                pila.pop();
                pila.push(puntos[i]);
            }
        }
    }

    cout << "Los puntos mas cercanos al origen son: " << endl;
    while (!pila.empty())
    {
        cout << pila.top().first << "," << pila.top().second << endl;
        pila.pop();
    }
}

crear lista de distancias con list comprehension

distancias=[(i[0]**2+i[1]**2)**(1/2) for i in puntos]