好久沒發每日leetcode了
終於遇到一題我會寫的
786. K-th Smallest Prime Fraction
給一個質數矩陣，第一個元素是1
請回傳第k小的分子分母組合
思路 :
最簡單的方法
把全部小於1的組合都找出來，再進行排序就好
不然就是利用最小堆找出第k小的組合
這樣時間複雜度就會變成klog(n)
一開始先把分子為1的組合丟到heap裡面
pop k次，每次pop出來後就更新分子再丟進去
GOLANG CODE :
var ARR []int
type h [][]int
func (this h) Swap(i, j int) {
this[i], this[j] = this[j], this[i]
}
func (this h) Len() int {
return len(this)
}
func (this h) Less(i, j int) bool {
return float64(ARR[this[i][0]])/float64(ARR[this[i][1]]) < float64(ARR[this[j
][0]])/float64(ARR[this[j][1]])
}
func (this *h) Pop() interface{} {
n := (*this)[len(*this)-1]
(*this) = (*this)[:len(*this)-1]
return n
}
func (this *h) Push(x interface{}) {
(*this) = append(*this, x.([]int))
}
func kthSmallestPrimeFraction(arr []int, k int) []int {
ARR = arr
h := h(make([][]int, 0))
n := len(arr)
for i := 1; i < n; i++ {
heap.Push(&h, []int{0, i})
}
for i := 0; i < k-1; i++ {
tmp := heap.Pop(&h).([]int)
if tmp[0]+1 != tmp[1] {
heap.Push(&h, []int{tmp[0] + 1, tmp[1]})
}
}
ans := heap.Pop(&h).([]int)
return []int{arr[ans[0]], arr[ans[1]]}
}
GOLANG 的heap有夠難寫