378.md

Kth Smallest Element in a Sorted Matrix

解法一

多路归并

func kthSmallest4(matrix [][]int, k int) int {
   if len(matrix) ==0 {
       return 0
   }

   heapSpec := new(BDS.IntHeapSpec) // github.com/googege/BDS

   //init 初始化这个小顶堆。
   for i := 0; i < len(matrix); i++ {

   	l := [3]int{
   		i, 0, matrix[i][0],
   	}

   	heapSpec.Push(l)

   }
   // 使用对路归并原理（min(min1,min2,min3)）
   for i := 1; i <= k-1; i++ {

   	result := heap.Pop(heapSpec).([3]int)
   	if result[0] < len(matrix) && result[1] < len(matrix[0])-1 {
   		heap.Push(heapSpec, [3]int{result[0], result[1] + 1, matrix[result[0]][result[1]+1]})
   	}

   }
   return heapSpec.Top().([3]int)[2]
}