法國我，怎麼是hard
我不想寫每日了
632. Smallest Range Covering Elements from K Lists
有k個lists依照non-decreasing的方式排列
請找到最小的range 可以包含所有lists至少一個元素
定義[a,b]比[c,d]小，b-a < d-c 或是 a<c如果 b-a == d-c
思路:
(1)可以用merge sort把所有list合在一起，再用sliding windows去找最小range
(2)
用minimun heap，從每個list抓一個元素放到heap裡
並記錄最大值
每次都從heap pop中一個元素，如果pop出來的元素屬於lists[i]
就再從lists[i] push一個元素進去
並且看目前heap裡的最大值和最小值相差多少
每次都要更新最大值
這樣也可以得到答案
golang code :
type IntHeap [][2]int
func (h IntHeap) Len() int { return len(h) }
func (h IntHeap) Less(i, j int) bool { return h[i][0] < h[j][0] }
func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }
func (h *IntHeap) Push(x interface{}) {
// Push and Pop use pointer receivers because they modify the slice's length,
// not just its contents.
*h = append(*h, x.([2]int))
}
func (h *IntHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0 : n-1]
return x
}
func smallestRange(nums [][]int) []int {
idx, min_diff, ans := make([]int, len(nums)), math.MaxInt64, []int{math.
MaxInt64, math.MinInt64}
min_heap := &IntHeap{}
for i := 0; i < len(nums); i++ {
idx[i] = 1
heap.Push(min_heap, [2]int{nums[i][0], i})
ans[1] = max(ans[1], nums[i][0])
}
ans[0] = (*min_heap)[0][0]
rec := ans[1]
min_diff = ans[1] - ans[0]
for {
tmp := heap.Pop(min_heap).([2]int)
if idx[tmp[1]] == len(nums[tmp[1]]) {
break
} else {
heap.Push(min_heap, [2]int{nums[tmp[1]][idx[tmp[1]]], tmp[1]})
rec = max(rec, nums[tmp[1]][idx[tmp[1]]])
if rec-(*min_heap)[0][0] < min_diff {
min_diff = rec - (*min_heap)[0][0]
ans[0] = (*min_heap)[0][0]
ans[1] = rec
}
idx[tmp[1]]++
}
}
return ans
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.214.188 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1728810739.A.733.html