第-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

题解

思路同 373. 查找和最小的-k-对数字

/**
 * @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]]
  }
}