字节跳动面试算法题解析（go)
//问题描述：合并多个有序数组
//Input:
// [
// [1, 3, 5, 7],
// [2, 4, 6],
// [0, 8, 9, 10, 11]
// ]
//Output: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
/思路解析：这里使用优先队列，即创建小根堆
//时间复杂度为O（NlogK)
type Node struct {
row int
col int
val int
}
type NodeHeap []Node
func (h NodeHeap) Len() int{
return len(h)
}
func (h NodeHeap) Less(i, j int) bool{
return h[i].val < h[j].val
}
func (h NodeHeap) Swap(i, j int) {
h[i], h[j] = h[j], h[i]
}
func (h *NodeHeap) Push(x interface{}) {
*h = append(*h, x.(Node))
}
func (h *NodeHeap) Pop() interface{} {
old := *h
n := len(old)
x := old[n-1]
*h = old[0: n-1]
return x
}
func mergekSortedArrays (arrays [][]int) []int {
// write your code here
//var priorityQueue interface
h := &NodeHeap{}
heap.Init(h)
ans := []int{}
for i := 0; i < len(arrays); i++{
node := &Node{
row: i,
col: 0,
val: arrays[i][0],
}
heap.Push(h, *node)
}
//fmt.Println(h)
for h.Len() != 0{
n := heap.Pop(h) //返回的一个接口
ans = append(ans, n.(Node).val) //适用类型断言将接口转换为Node类型
if n.(Node).col+1 < len(arrays[n.(Node).row]) {
//定义新添加的节点
newNode := &Node{
row: n.(Node).row,
col: n.(Node).col+1,
val: arrays[n.(Node).row][n.(Node).col+1],
}
heap.Push(h,*newNode)
}
}
return ans
}
func main(){
arrays := [][]int{{1,3,5,7},{2,4,6},{0,8,9,10,11}}
fmt.Println(mergekSortedArrays(arrays))
}