Programando K Closest Points to Origin con Python

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

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

Tomar examen

Cursos Empresas Blog Live Conf Eventos Precios

0:0010:45

Programando K Closest Points to Origin con Python

Curso de Algoritmos Avanzados: Estructuras de Datos Lineales

Clase 28 de 34

Clase 28 / 34

Hans Arias

Hace 3 años

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

}

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

Programando Odd Even Linked List con C++

Linked List Cycle: análisis del problema

Solución de Linked List Cycle

Programando Linked List Cycle con Python

Palindrome Linked List: análisis del problema

Solución de 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

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

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

Programando K Closest Points to Origin con Python

Reorganize String: análisis del problema

Solución de 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

Programando K Closest Points to Origin con Python