LeetCode 973. 最接近原点的 K 个点

Categories:

题目描述
思路分析
1. 解法一：最大堆（推荐）
相似题目

题目描述

✅ 973. 最接近原点的 K 个点

思路分析

解法一：最大堆（推荐）

核心思路：

维护大小为 k 的最大堆，堆顶为当前最远点。

遍历点集，若新点更近则替换堆顶。

堆中剩余点即为答案。

复杂度分析：

时间复杂度：O(n log k)。

空间复杂度：O(k)。

import java.util.PriorityQueue;

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> dist(b) - dist(a));

        for (int[] p : points) {
            if (heap.size() < k) {
                heap.offer(p);
            } else if (dist(p) < dist(heap.peek())) {
                heap.poll();
                heap.offer(p);
            }
        }

        int[][] res = new int[k][2];
        for (int i = 0; i < k; i++) {
            res[i] = heap.poll();
        }

        return res;
    }

    private int dist(int[] p) {
        return p[0] * p[0] + p[1] * p[1];
    }
}

import "container/heap"

type Point struct {
	x int
	y int
}

type MaxHeap []Point

func (h MaxHeap) Len() int { return len(h) }
func (h MaxHeap) Less(i, j int) bool { return dist(h[i]) > dist(h[j]) }
func (h MaxHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *MaxHeap) Push(x interface{}) { *h = append(*h, x.(Point)) }
func (h *MaxHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[:n-1]
	return x
}

func kClosest(points [][]int, k int) [][]int {
	h := &MaxHeap{}
	heap.Init(h)

	for _, p := range points {
		pt := Point{x: p[0], y: p[1]}
		if h.Len() < k {
			heap.Push(h, pt)
		} else if dist(pt) < dist((*h)[0]) {
			heap.Pop(h)
			heap.Push(h, pt)
		}
	}

	res := make([][]int, k)
	for i := 0; i < k; i++ {
		pt := heap.Pop(h).(Point)
		res[i] = []int{pt.x, pt.y}
	}

	return res
}

func dist(p Point) int {
	return p.x*p.x + p.y*p.y
}

相似题目

题目	难度	考察点
215. 数组中的第K个最大元素	中等	堆
347. 前 K 个高频元素	中等	堆
378. 有序矩阵中第 K 小的元素	中等	堆
658. 找到 K 个最接近的元素	中等	二分
973. 最接近原点的 K 个点	中等	堆

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2022/82302161