Playground: K Closest Points to Origin

Clase 33 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

John Eduard Meneses González

student•

My Solution!!

Carlos Hernandez

student•

Mi solución (sin usar heapq, ya que no estoy familiarizado, ahora veré la de la profe para ver cómo sería con ese enfoque):

import heapq
from typing import List

def kClosest(points: List[List[int]], K: int) -> List[List[int]]:
   distances = {}
   counter = 0

   for point in points:
      x, y = point[0], point[1]
      distance = (x * x + y * y) ** (0.5)
      distances[counter] = distance
      counter += 1

   distances = dict(sorted(distances.items(), key=lambda item:item[1]))

   counter = 0

   result = []
   for key in distances.keys():
      result.append(points[key])
      counter += 1
      if (counter == K):
         break

   return result

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

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

Carlos Hernandez

student•

Ahora usando heapq:

def kClosest(points: List[List[int]], k: int) -> List[List[int]]:
   distances = []
   for point in points:
      x, y = point[0], point[1]
      distance = (x * x + y * y) ** (0.5)
      heapq.heappush(distances, (distance, [x, y]))

   smallest = heapq.nsmallest(k, distances)
   result = []
   for distance, point in smallest:
      result.append(point)
   return result

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

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

Miguel Angel Reyes Moreno

student•

propuesta:

import heapqfrom typing import List def kClosest(puntos: List[List[int]], K: int) -> List[List[int]]: heap = [] for punto in puntos: x, y = punto distancia_cuadrada = x*x + y*y heapq.heappush(heap, (-distancia_cuadrada, punto)) if len(heap) > K: heapq.heappop(heap) return [punto for _, punto in heap] response = kClosest([[1,3], [3,4], [5,6]], 1)print(response) response = kClosest([[13,-8], [1,20], [-5,5]], 2)print(response)

Yojan Antonio Pardo Zabala

student•

mi solución

import heapq
from typing import List

def kClosest(puntos: List[List[int]], K: int) -> List[List[int]]:
   # Tu código aquí 👇
   min_heap = []
   for (x,y) in puntos:
      dist = x**2 + y**2
      heapq.heappush(min_heap, (dist, [x, y]))

   closest_points = []

   for _ in range(K):
      closest_points.append(heapq.heappop(min_heap)[1])

   return closest_points

Rafael Estiven Uribe Álvarez

student•

Mi respuesta:

Luis Antonio Ibarra Salgado

student•

Use la func 'dist' del modulo math para sacar las distancias

import heapq
from math import dist
from typing import List

def kClosest(puntos: List[List[int]], K: int) -> List[List[int]]:
   min_heap = []

   for p in puntos:
      distance = -(dist((0,0), p))
      if len(min_heap) < K:
         heapq.heappush(min_heap, (distance, p))
      else:
         if distance > min_heap[0][0]:
            heapq.heapreplace(min_heap, (distance, p))
   return [i[1] for i in min_heap]

Nicolas Alpargatero

student•

No sé porque no funciono en el playground, decía que error al llamar list pero bueno funcionó, toco con ayuda:

import heapq
from typing import List

def kClosest(points: List[List[int]], K: int) -> List[List[int]]:
   distances = {}
   counter = 0

   for point in points:
      x, y = point[0], point[1]
      distance = (x * x + y * y) ** (0.5)
      distances[counter] = distance
      counter += 1

   distances = dict(sorted(distances.items(), key=lambda item:item[1]))

   counter = 0

   result = []
   for key in distances.keys():
      result.append(points[key])
      counter += 1
      if (counter == K):
         break

   return result

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

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

def kClosest(points: List[List[int]], k: int) -> List[List[int]]:
   distances = []
   for point in points:
      x, y = point[0], point[1]
      distance = (x * x + y * y) ** (0.5)
      heapq.heappush(distances, (distance, [x, y]))

   smallest = heapq.nsmallest(k, distances)
   result = []
   for distance, point in smallest:
      result.append(point)
   return result

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

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

import heapq
from typing import List

def kClosest(puntos: List[List[int]], K: int) -> List[List[int]]:
   # Tu código aquí 👇
   min_heap = []
   for (x,y) in puntos:
      dist = x**2 + y**2
      heapq.heappush(min_heap, (dist, [x, y]))

   closest_points = []

   for _ in range(K):
      closest_points.append(heapq.heappop(min_heap)[1])

   return closest_points

import heapq
from math import dist
from typing import List

def kClosest(puntos: List[List[int]], K: int) -> List[List[int]]:
   min_heap = []

   for p in puntos:
      distance = -(dist((0,0), p))
      if len(min_heap) < K:
         heapq.heappush(min_heap, (distance, p))
      else:
         if distance > min_heap[0][0]:
            heapq.heapreplace(min_heap, (distance, p))
   return [i[1] for i in min_heap]

Playground: K Closest Points to Origin

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