好久没发每日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有够难写

大师

你是大师

大师我会想先排序 小至大=A[] 大至小=B[]然后A[i]/B[j]

大师