统计输入自然数m的所有素数因子（leetcode786go第K个最小的素数分数）

给你一个按递增顺序排序的数组 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问题