給你一個按遞增順序排序的數組 arr 和一個整數 k 。數組 arr 由 1 和若幹 素數 組成，且其中所有整數互不相同。

對于每對滿足 0 <= i < j < arr.length 的 i 和 j ，可以得到分數 arr[i] / arr[j] 。

那麼第 k 個最小的分數是多少呢? 以長度為 2 的整數數組返回你的答案, 這裡 answer[0] == arr[i] 且 answer[1] == arr[j] 。

示例 1：輸入：arr = [1,2,3,5], k = 3 輸出：[2,5]

解釋：已構造好的分數,排序後如下所示:

1/5, 1/3, 2/5, 1/2, 3/5, 2/3

很明顯第三個最小的分數是 2/5

示例 2：輸入：arr = [1,7], k = 1 輸出：[1,7]

提示：2 <= arr.length <= 1000

1 <= arr[i] <= 3 * 104

arr[0] == 1

arr[i] 是一個 素數 ，i > 0

arr 中的所有數字 互不相同 ，且按 嚴格遞增 排序

1 <= k <= arr.length * (arr.length - 1) / 2

1、自定義排序；時間複雜度O(n^2log(n))，空間複雜度O(n^2)

func kthSmallestPrimeFraction(arr []int, k int) []int { n := len(arr) nums := make([][]int, 0) for i := 0; i < n; i { for j := i 1; j < n; j { nums = append(nums, []int{arr[i], arr[j]}) } } sort.Slice(nums, func(i, j int) bool { // a/b c/d => ad<bc a, b, c, d := nums[i][0], nums[i][1], nums[j][0], nums[j][1] return a*d < b*c }) return nums[k-1] }

2、堆；時間複雜度O(nlog(n))，空間複雜度O(n)

func kthSmallestPrimeFraction(arr []int, k int) []int { n := len(arr) intHeap := make(IntHeap, 0) heap.Init(&intHeap) for j := 1; j < n; j { heap.Push(&intHeap, []int{arr[0], arr[j], 0, j}) // 0/j 遞減：分子最小，分母依次增大 } for i := 1; i <= k-1; i { // 取k-1個數(k從1開始) node := heap.Pop(&intHeap).([]int) x, y := node[2], node[3] if x 1 < y { // 下标 x 1 < y heap.Push(&intHeap, []int{arr[x 1], arr[y], x 1, y}) } } return []int{intHeap[0][0], intHeap[0][1]} } type IntHeap [][]int func (h IntHeap) Len() int { return len(h) } func (h IntHeap) Less(i, j int) bool { return h[i][0]*h[j][1] < h[i][1]*h[j][0] } // a*d < b*c func (h IntHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] } func (h *IntHeap) Push(x interface{}) { *h = append(*h, x.([]int)) } func (h *IntHeap) Pop() interface{} { old := *h n := len(old) x := old[n-1] *h = old[0 : n-1] return x }

3、二分查找；時間複雜度O(nlog(n))，空間複雜度O(1)

func kthSmallestPrimeFraction(arr []int, k int) []int { n := len(arr) left, right := 0.0, 1.0 for { mid := left (right-left)/2 count := 0 x, y := 0, 1 // 記錄最大的分子/分母 i := -1 for j := 1; j < n; j { for float64(arr[i 1])/float64(arr[j]) < mid { // 小于目标 i if arr[i]*y > arr[j]*x { // 更新：a/b > c/d => a*d > bc 保存a,b x, y = arr[i], arr[j] } } count = count (i 1) // 除以當前arr[j],總計幾個數小于mid } if count == k { return []int{x, y} } else if count < k { left = mid } else { right = mid } } }

Hard題目，top K問題

更多精彩资讯请关注tft每日頭條，我们将持续为您更新最新资讯!