373. Find K Pairs with Smallest Sums
有两个array nums1、nums2以递增的顺序排序
定义分别从nums1、nums2各取一个元素所组成的组合[nums1[i]、nums2[j]]
请回传前k总和最小的组合
思路:
因为nums1、nums2是以递增顺序排列
所以最小的组合一定是[nums1[0]、nums2[0]]
那第二小的组合会是[nums1[0]、nums2[1]] or [nums1[1]、nums2[0]]其中一个
以此类推[nums1[i]、nums2[j]]下一个的组合会是
[nums1[i+1]、nums2[j]] or [nums1[i]、nums2[j+1]]中的一个
知道了这个关系，我们就可以用heap来找到k个最小的组合
然后要记得纪录每个放进去heap的组合，避免重复放入
golang code :
type h [][2]int
var arr1 []int
var arr2 []int
func (this h) Swap(i, j int) {
this[i], this[j] = this[j], this[i]
}
func (this h) Less(i, j int) bool {
return arr1[this[i][0]]+arr2[this[i][1]] < arr1[this[j][0]]+arr2[this[j][1]]
}
func (this h) Len() int {
return len(this)
}
func (this *h) Push(x interface{}) {
(*this) = append(*this, x.([2]int))
}
func (this *h) Pop() interface{} {
n := len(*this) - 1
res := (*this)[n]
(*this) = (*this)[:n]
return res
}
func kSmallestPairs(nums1 []int, nums2 []int, k int) [][]int {
rec := make(map[[2]int]bool)
arr1 = nums1
arr2 = nums2
ans := make([][]int, 0)
hp := h([][2]int{})
heap.Push(&hp, [2]int{0, 0})
for k > 0 {
temp := heap.Pop(&hp).([2]int)
ans = append(ans, []int{nums1[temp[0]], nums2[temp[1]]})
if temp[1]+1 < len(nums2) && !rec[[2]int{temp[0], temp[1] + 1}] {
heap.Push(&hp, [2]int{temp[0], temp[1] + 1})
rec[[2]int{temp[0], temp[1] + 1}] = true
}
if temp[0]+1 < len(nums1) && !rec[[2]int{temp[0] + 1, temp[1]}] {
heap.Push(&hp, [2]int{temp[0] + 1, temp[1]})
rec[[2]int{temp[0] + 1, temp[1]}] = true
}
k