Open
Description
973. K Closest Points to Origin
Problem Solving
Buggy Code
from heapq import heapreplace, heapify
class Solution(object):
def kClosest(self, pairs, k):
nums = []
dic = {}
self.getDist(pairs, nums, dic)
nums = [-num for num in nums]
heap = nums[:k]
heapq.heapify(heap)
for i in range(k, len(nums)):
if nums[i] > heap[0]:
heapq.heapreplace(heap, nums[i])
res = []
for num in heap:
res.append(dic[-num])
return res
def getDist(self, pairs, nums, dic):
for pair in pairs:
x, y = pair
dist = (x ** 2 + y ** 2) ** 0.5
dic[dist] = [x, y]
nums.append(dist)
Fail:
Input
[[0,1],[1,0]]
2
Output
[[1,0],[1,0]]
Expected
[[0,1],[1,0]]
Fixed Code
from heapq import heapreplace, heapify
class Solution(object):
def kClosest(self, pairs, k):
nums = []
self.getDist(pairs, nums)
heap = nums[:k]
heapq.heapify(heap)
for i in range(k, len(nums)):
if -nums[i][0] < -heap[0][0]:
heapq.heapreplace(heap, nums[i])
res = []
for num, x, y in heap:
res.append([x, y])
return res
def getDist(self, pairs, nums):
for pair in pairs:
x, y = pair
dist = (x ** 2 + y ** 2) ** 0.5
nums.append((-dist, x, y))
Metadata
Metadata
Assignees
Labels
No labels