973. K Closest Points to Origin

Question: K Closest Points to Origin

Solution1

想法：

最近的 k 個值 → 按照順序存 k 個 element → 超過長度 k 就把大的拿掉 → pop 掉大的值 → Max Heap of size k

因為圓半徑以內的距離都一樣，代表相同距離可能會有多個點，因此 Max Heap 存 distance，再另外用一個 Hashmap 存 distance 對應的 points

import heapq

from collections import defaultdict

import math

class Solution:

def kClosest(self, points: list[list[int]], k: int) -> list[list[int]]:

distance_points = defaultdict(list)

min_distance = list()

heapq.heapify(min_distance)

ans = list()

for x, y in points:

d = math.sqrt(x ** 2 + y ** 2)

distance_points[d].append([x, y])

heapq.heappush(min_distance, -d)

if len(min_distance) > k:

heapq.heappop(min_distance)

min_distance = set(list(min_distance))

for d in min_distance:

for ele in distance_points[-d]:

ans.append(ele)

return ans

Solution2 (NeetCode 解法)

想法：

最近的 k 個值 → 由小到大存全部的 element → pop 出 k 個最小值 → Min Heap

heapq.heapify Time Complexity O(n)，但 heapq.heappush 的 Time Complexity 是 O(nlogn)

所以先把 element 都存在 list 中後，在用 heapify 去製作 minHeap，會比邊 for loop 每一個 element，邊 heappush 每一個 element 的時間複雜度好（Solution 1）。

排好之後要 pop k 個 element 出來，pop 一次的 Time Complexity 是 O(logn) 所以總共是 k * O( logn)

k logn < n logn 所以用 minHeap 是比較好的選擇

class Solution:

def kClosest(self, points: list[list[int]], k: int) -> list[list[int]]:

min_heap = list()

for x, y in points:

d = x ** 2 + y ** 2

min_heap.append([d, x, y])

heapq.heapify(min_heap)

res = list()

for i in range(k):

d, x, y = heapq.heappop(min_heap)

res.append([x, y])

return res

Video Solution