Programando K Closest Points to Origin con Python

Clase 34 de 41 • Curso de Algoritmos Avanzados: Estructuras de Datos Lineales

Contenido del curso

Introducción

1
¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?
00:52 min

Lista Enlazada

Pilas y colas

Colas de prioridad

Próximos pasos

41
Toma el Curso Avanzado de Algoritmos: Grafos y Árboles
00:33 min

Tomar examen

Comentarios

Erick Escobar

student•

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)

REYNALDO FABIAN NORIEGA ZAMBRANO

student•

Aporte en C++, me dio pereza crear una funcion aparte xD:

#include<iostream>
#include<vector>
#include<queue>


int main(){

	int k = 2;
	std::vector<std::pair<int,int>> output;
	std::vector<std::pair<int,int>> input = {{1,3}, {-2,7}, {3,4}, {-10,1}};
	std::priority_queue<std::pair<float, std::pair<int,int>>, std::vector<std::pair<float, std::pair<int,int>>>, std::greater<>> min_q;

	for(auto p: input){
		float d = p.first*p.first + p.second*p.second;
		std::pair<float, std::pair<int,int>> np;
		np.first = d;
		np.second = p;
		min_q.push(np);
	}


	while(k-- && !min_q.empty()){
		output.push_back(min_q.top().second);
		min_q.pop();
	}
	return 0;
}

Alejandro Marín

student•

heapq tiene un método llamado nsmallest que permite obtener un número determinado de los valores más pequeños. Este método recibe un iterable y, de forma interna, construye su propio heap (cola de prioridad).

Se puede lograr el mismo resultado en una sola línea (aunque puede resultar poco legible para quienes no están familiarizados con Python) utilizando heapq.nsmallest, una list comprehension y un generador.

def kClosest(points, k):
    return [p for _, p in heapq.nsmallest(k, ((x**2 + y**2, [x, y]) for x, y in points))]

John Eduard Meneses González

student•

My solution!!

Yojan Antonio Pardo Zabala

student•

Esta es mi solución en java, utilicé un PriorityQueue

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<k; i++){
            result[i] = queue.poll();
        }

        return result;
    }
}

Juan Pablo Reina Gutierrez

student•

Esta es mi solución en Java:

Hans Arias

student•

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

}

Nicolas Alpargatero

student•

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

Tomás Santa Cruz

student•

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();
    }
}

Gabriel Revelo

student•

crear lista de distancias con list comprehension

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

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)

#include<iostream>
#include<vector>
#include<queue>


int main(){

	int k = 2;
	std::vector<std::pair<int,int>> output;
	std::vector<std::pair<int,int>> input = {{1,3}, {-2,7}, {3,4}, {-10,1}};
	std::priority_queue<std::pair<float, std::pair<int,int>>, std::vector<std::pair<float, std::pair<int,int>>>, std::greater<>> min_q;

	for(auto p: input){
		float d = p.first*p.first + p.second*p.second;
		std::pair<float, std::pair<int,int>> np;
		np.first = d;
		np.second = p;
		min_q.push(np);
	}


	while(k-- && !min_q.empty()){
		output.push_back(min_q.top().second);
		min_q.pop();
	}
	return 0;
}

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<k; i++){
            result[i] = queue.poll();
        }

        return result;
    }
}

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

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

}

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

Programando K Closest Points to Origin con Python

Introducción

¿Ya tomaste el Curso Avanzado de Algoritmos: Patrones de Arrays y Strings?

Lista Enlazada

Estructura de datos: Lista Enlazada

Programando listas enlazadas con Java

Cómo Invertir una Lista Enlazada

Odd Even Linked List: análisis del problema

Solución de Odd Even Linked List

Playground: Odd Even Liked List

Programando Odd Even Linked List con C++

Linked List Cycle: análisis del problema

Solución de Linked List Cycle

Playground: Linked List Cycle

Programando Linked List Cycle con Python

Palindrome Linked List: análisis del problema

Solución de Palindrome Linked List

Playground: Palindrome Linked List

Programando Palindrome Linked List con Java

Reorder List: análisis del problema

Solución de Reorder List

Programando Reorder List con JavaScript

Playground: Reorder List Without Repeated Values

Reto: LRU Caché

Ejercicios Prácticos con Listas Enlazadas y Historial de Navegador

Operaciones con Listas Enlazadas: Suma, Intercambio y Navegador

Pilas y colas

Estructura de datos: Pilas y Colas

Paréntesis Válido: análisis del problema

Solución de Paréntesis Válido

Playground: Paréntesis Válido

Programando Paréntesis Válido con C++

Comparación de Cadenas con Backspaces

Colas de prioridad

Estructura de datos: Colas de Prioridad

K Closest Points to Origin: análisis del problema

Solución de K Closest Points to Origin

Playground: K Closest Points to Origin

Programando K Closest Points to Origin con Python

Reorganize String: análisis del problema

Solución de Reorganize String

Playground: Reorganize String

Programando Reorganize String con Python

Colas de Prioridad: Ejercicios Prácticos y Soluciones

Colas de Prioridad y Gestión de Eventos

Próximos pasos

Toma el Curso Avanzado de Algoritmos: Grafos y Árboles