Introducción

1

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

Lista Enlazada

2

Estructura de datos: Lista Enlazada

3

Programando listas enlazadas con Java

4

Cómo Invertir una Lista Enlazada

5

Odd Even Linked List: análisis del problema

6

Solución de Odd Even Linked List

7

Playground: Odd Even Liked List

8

Programando Odd Even Linked List con C++

9

Linked List Cycle: análisis del problema

10

Solución de Linked List Cycle

11

Playground: Linked List Cycle

12

Programando Linked List Cycle con Python

13

Palindrome Linked List: análisis del problema

14

Solución de Palindrome Linked List

15

Playground: Palindrome Linked List

16

Programando Palindrome Linked List con Java

17

Reorder List: análisis del problema

18

Solución de Reorder List

19

Programando Reorder List con JavaScript

20

Playground: Reorder List Without Repeated Values

21

Reto: LRU Caché

22

Ejercicios recomendados de Lista Enlazada

23

Ejercicios resueltos de Lista Enlazada

Pilas y colas

24

Estructura de datos: Pilas y Colas

25

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

26

Solución de Paréntesis Válido

27

Playground: Paréntesis Válido

28

Programando Paréntesis Válido con C++

29

Ejercicios recomendados de Pilas

Colas de prioridad

30

Estructura de datos: Colas de Prioridad

31

K Closest Points to Origin: análisis del problema

32

Solución de K Closest Points to Origin

33

Playground: K Closest Points to Origin

34

Programando K Closest Points to Origin con Python

35

Reorganize String: análisis del problema

36

Solución de Reorganize String

37

Playground: Reorganize String

38

Programando Reorganize String con Python

39

Ejercicios recomendados de Colas de prioridad

40

Ejercicios resueltos de Colas de prioridad

Próximos pasos

41

Toma el Curso Avanzado de Algoritmos: Grafos y Árboles

No tienes acceso a esta clase

¡Continúa aprendiendo! Únete y comienza a potenciar tu carrera

¡Se acaba el precio especial! Aprende Inglés, AI, programación y más.

Antes: $249

Currency
$209
Suscríbete

Termina en:

1 Días
10 Hrs
4 Min
25 Seg

Programando K Closest Points to Origin con Python

34/41
Recursos

Aportes 7

Preguntas 0

Ordenar por:

¿Quieres ver más aportes, preguntas y respuestas de la comunidad?

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: ![](https://static.platzi.com/media/user_upload/imagen-d8e73658-fedf-4cdf-9a67-df79e5e7abe0.jpg) ![](https://static.platzi.com/media/user_upload/imagen-66abc080-ce6c-46c4-b98e-57e3a1bfb2f0.jpg) ![](https://static.platzi.com/media/user_upload/imagen-9eade377-b739-41dc-80a8-37f10ab8fa72.jpg)

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]