K Closest Points to Origin: análisis del problema

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

K Closest Points to Origin: análisis del problema

Comentarios2

Nicolas Alpargatero

Estudiante

Problema: K Closest Points to Origin

Dada una matriz de puntos donde puntos[i] = [xi, yi] representa un punto del plano X-Y y un número entero k, devuelve los k puntos más cercanos al origen (0, 0)

La distancia entre dos puntos del plano X-Y es la distancia euclidiana.

Pues devolver la respuesta en cualquier orden. Se garantiza que la respuesta es única (excepto por el orden en que se encuentre).

Ejemplo:

[[1, 3], [-2, 7], [3, 4], [-10, 1]] k = 2 Output: [[1, 3], [3, 4]]

Investigando:

Hay un algoritmo llamado k-vecinos más cercanos (KNN) pero requiere de un Big O(n) para búsqueda lineal y/o de arboles para un O(log n) pero aún no llegamos allá.
Para implementar el caso toca estudiar la Liberia heaqp nombrada en la clase anterior.
- https://docs.python.org/es/3/library/heapq.html
- heapq.heappush para insertar los puntos en el heap según su distancia al origen.
- la función heapq.heappop para extraer los k puntos más cercanos.

Bryan Castano

Estudiante

Hiii Guys \n

Como dicese la Proffe.

Debe Usarse Heap como DSA..

Yo asumiria un ArrayX2D Matrix Arr[n][N] para guardar mis puntos cordenadas ( x¡, y¡ ) del plano Cartesiano sean guardados en int Arr[][] ;

luego se hace el calculo de la distancia Eucliliana d y se guardan en otro Array X1D comoo : int distance[N] ; \nLuego Yo llamo my >Function void getTopKElelments( int Arr[] , int arr.length , int k ) { // function bodty call to heapify } ,; \ndonde k es la cantidad de elementos cercanos al Origine (0,0) que quiero traer de mis puntos \nLuego hago las llamadas recursivas a Heapify para emplear la Heap como PriorityQueue en cuanto a la distancia al origne \n ahora quel o pienso Yo creo que nos podemos ahorrar el array distancias[n] en Memoria y hacer todos directamente desde la Matrix ArrayX2D que guardase los puntos Originales del Problema. \nPD. se debe hacer uso del Heap como Estructura de datos : complete tree [ aunque creo que eso es para el otro curso NoLineal Mas Avanzado ] \nde cualquier forma la complejidad Temporal segun veo estaria por =( nLogn ) \n

K Closest Points to Origin: análisis del problema

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