1 minute read

973. K Closest Points to Origin

문제 링크

https://leetcode.com/problems/k-closest-points-to-origin/description/

문제 설명

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(x1 - x2)2 + (y1 - y2)2).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

제한 사항

  • 1 <= k <= points.length <= 10^4
  • -10^4 <= xi, yi <= 10^4

입출력 예 #1

  1. Input : points = [[1,3],[-2,2]], k = 1
  2. Output : [[-2,2]]
  3. Explanation : The distance between (1, 3) and the origin is sqrt(10).

The distance between (-2, 2) and the origin is sqrt(8).

Since sqrt(8) < sqrt(10), (-2, 2) is closer to the origin.

We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].

입출력 예 #2

  1. Input : points = [[3,3],[5,-1],[-2,4]], k = 2
  2. Output : [[3,3],[-2,4]]
  3. Explanation : The answer [[-2,4],[3,3]] would also be accepted.

문제 풀이

각 배열의 항목의 유클리드 거리 순으로 정렬하고 K개 만큼 출력한다.

  1. heapq를 이용한 풀이
  2. 파이썬 정렬을 이용한 풀이
class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        heap = []
        for (x, y) in points:
            dist = x ** 2 + y ** 2
            heapq.heappush(heap, (dist, x, y))
        
        result = []
        for _ in range(k):
            (dist, x, y) = heapq.heappop(heap)
            result.append((x, y))
            
        return result

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        return sorted(points, key = lambda x: x[0]**2 + x[1]**2)[:k]

[[3, 3], [-2, 4]]

Comments

You May Also Enjoy