LeetCode 373. 查找和最小的 K 对数字

Categories:

Tags:

题目描述
思路分析
参考代码

题目描述

✅ 373. 查找和最小的 K 对数字

思路分析

最小堆

参考代码

type Pair struct {
	sum, i, j int
}

type MinHeap []Pair

func (h MinHeap) Len() int           { return len(h) }
func (h MinHeap) Less(i, j int) bool { return h[i].sum < h[j].sum }
func (h MinHeap) Swap(i, j int)      { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(Pair))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)
	x := old[n-1]
	*h = old[0 : n-1]
	return x
}

func kSmallestPairs(nums1 []int, nums2 []int, k int) [][]int {
	h := &MinHeap{}
	heap.Init(h)
	res := [][]int{}

	// 初始化堆
	for i := 0; i < len(nums1) && i < k; i++ {
		heap.Push(h, Pair{nums1[i] + nums2[0], i, 0})
	}

	// 取出最小的 k 个数对
	for k > 0 && h.Len() > 0 {
		pair := heap.Pop(h).(Pair)
		i, j := pair.i, pair.j
		res = append(res, []int{nums1[i], nums2[j]})
		k--
		if j+1 < len(nums2) {
			heap.Push(h, Pair{nums1[i] + nums2[j+1], i, j + 1})
		}
	}

	return res
}

write your code here

➡️ 点击查看 Java 题解

write your code here

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/54475263