上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution {
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
}
};
golang 解法, 执行用时: 124 ms, 内存消耗: 7.8 MB, 提交时间: 2020-11-09 14:10:45
type pair struct {
dist int
point []int
}
type hp []pair
func (h hp) Len() int { return len(h) }
func (h hp) Less(i, j int) bool { return h[i].dist > h[j].dist }
func (h hp) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(pair)) }
func (h *hp) Pop() interface{} { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }
func kClosest(points [][]int, k int) (ans [][]int) {
h := make(hp, k)
for i, p := range points[:k] {
h[i] = pair{p[0]*p[0] + p[1]*p[1], p}
}
heap.Init(&h) // O(k) 初始化堆
for _, p := range points[k:] {
if dist := p[0]*p[0] + p[1]*p[1]; dist < h[0].dist {
h[0] = pair{dist, p}
heap.Fix(&h, 0) // 效率比 pop 后 push 要快
}
}
for _, p := range h {
ans = append(ans, p.point)
}
return
}
python3 解法, 执行用时: 752 ms, 内存消耗: 19.1 MB, 提交时间: 2020-11-09 12:01:13
class Solution:
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
'''用堆排序的方式'''
q = [(-x**2 - y**2, i) for i, (x,y) in enumerate(points[:K])]
heapq.heapify(q) # 堆化(排序)
for j in range(K, len(points)):
x, y = points[j]
dis = -x**2-y**2
if dis > q[0][0]:
heapq.heappushpop(q, (dis, j))
return [points[t] for (_, t) in q]
golang 解法, 执行用时: 140 ms, 内存消耗: 8.1 MB, 提交时间: 2020-11-09 10:49:28
func kClosest(points [][]int, K int) [][]int {
sort.Slice(points, func (i,j int)bool{
return points[i][0] * points[i][0] + points[i][1] * points[i][1] < points[j][0] * points[j][0] + points[j][1] * points[j][1]
})
return points[:K]
}
python3 解法, 执行用时: 636 ms, 内存消耗: 18.8 MB, 提交时间: 2020-11-09 10:39:08
class Solution:
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:
points.sort(key=lambda point: point[0]*point[0]+point[1]*point[1])
return points[:K]
