第-k-个最小的素数分数
Tips
题目类型: TopK
题目
给你一个按递增顺序排序的数组 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]
.
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
示例
输入: arr = [1, 2, 3, 5], k = 3
输出: [2, 5]
解释: 已构造好的分数,排序后如下所示:
1/5, 1/3, 2/5, 1/2, 3/5, 2/3
很明显第三个最小的分数是 2/5
题解
/**
* @param {number[]} arr
* @param {number} k
* @return {number[]}
*/
var kthSmallestPrimeFraction = function (arr, k) {
const n = arr.length
const pq = new MinHeap()
for (let i = 1; i < n; i++) {
pq.offer([arr[0] / arr[i], 0, i])
}
let curr = null
while (pq.size > 0 && k-- > 0) {
curr = pq.poll()
if (curr[1] < curr[2] - 1) {
pq.offer([arr[curr[1] + 1] / arr[curr[2]], curr[1] + 1, curr[2]])
}
}
return [arr[curr[1]], arr[curr[2]]]
}
class MinHeap {
constructor(compare = (a, b) => a[0] - b[0] < 0) {
this.data = []
this.size = 0
this.compare = compare
}
peek() {
return this.size === 0 ? null : this.data[0]
}
offer(val) {
this.data.push(val)
this._shifUp(this.size++)
}
poll() {
if (this.size === 0) {
return null
}
this._swap(0, --this.size)
this._shifDown(0)
return this.data.pop()
}
_parent(index) {
return (index - 1) >> 1
}
_child(index) {
return (index << 1) + 1
}
_shifDown(index) {
while (this._child(index) < this.size) {
let child = this._child(index)
if (
child + 1 < this.size &&
this.compare(this.data[child + 1], this.data[child])
) {
child = child + 1
}
if (this.compare(this.data[index], this.data[child])) {
break
}
this._swap(index, child)
index = child
}
}
_shifUp(index) {
while (
this._parent(index) >= 0 &&
this.compare(this.data[index], this.data[this._parent(index)])
) {
this._swap(index, this._parent(index))
index = this._parent(index)
}
}
_swap(a, b) {
;[this.data[a], this.data[b]] = [this.data[b], this.data[a]]
}
}