Re: [閒聊] 每日leetcode

[JIWP (神楽めあ的錢包)]

好久沒發每日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有夠難寫

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.71.213.102 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715351967.A.B83.html
推 SecondRun: 大師
推 sustainer123: 你是大師
→ Renxingshi: 大師
→ Renxingshi: 我會想先排序 小至大=A[] 大至小=B[]
→ Renxingshi: 然後A[i]/B[j]
→ digua: 大師