You are given a sorted integer array arr containing 1 and prime numbers, where all the integers of arr are unique. You are also given an integer k.
For every i and j where 0 <= i < j < arr.length, we consider the fraction arr[i] / arr[j].
Return the kth smallest fraction considered. Return your answer as an array of integers of size 2, where answer[0] == arr[i] and answer[1] == arr[j].
Example 1:
Input: arr = [1,2,3,5], k = 3
Output: [2,5]
Explanation: The fractions to be considered in sorted order are:
1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.
The third fraction is 2/5.
Example 2:
Input: arr = [1,7], k = 1
Output: [1,7]
Constraints:
- 2 <= arr.length <= 1000
- 1 <= arr[i] <= 3 * 104
- arr[0] == 1
- arr[i] is a prime number for i > 0.
- All the numbers of arr are unique and sorted in strictly increasing order.
- 1 <= k <= arr.length * (arr.length - 1) / 2
建议做这题之前去看一下这篇文章https://leetcode.com/problems/k-th-smallest-prime-fraction/discuss/115819/Summary-of-solutions-for-problems-%22reducible%22-to-LeetCode-378, 我没有完全看完， 但是我觉得这是我看过的对这类有序矩阵取第 nth 大或第 nth 小的问题最好的总结文章了。
我用的方法应该算是文章中作者所说的PriorityQueue-based solution with optimization方法， 整体来说就是建一个池子， 把当前最小(最大)的元素都放到这个池子里， 每次从这个池子里取出最小(最大)的元素， 同时再补充下一个最小(最大)元素进去。 这样我们第 k 次取出的元素就是我们要的答案
#[derive(Eq, PartialEq)]
struct Fraction(i32, i32, usize);
impl PartialOrd for Fraction {
fn partial_cmp(&self, other: &Self) -> Option<std::cmp::Ordering> {
Some((self.0 * other.1).cmp(&(self.1 * other.0)))
}
}
impl Ord for Fraction {
fn cmp(&self, other: &Self) -> std::cmp::Ordering {
self.partial_cmp(other).unwrap()
}
}
impl Solution {
pub fn kth_smallest_prime_fraction(arr: Vec<i32>, k: i32) -> Vec<i32> {
let mut indices = vec![0usize; arr.len()];
let mut heap = BinaryHeap::new();
let mut count = 1;
for i in 0..arr.len() {
heap.push(Reverse(Fraction(arr[0], arr[i], i)));
}
while count < k {
let Reverse(Fraction(_, _, i)) = heap.pop().unwrap();
if indices[i] < arr.len() - 1 {
indices[i] += 1;
heap.push(Reverse(Fraction(arr[indices[i]], arr[i], i)));
}
count += 1;
}
let Reverse(Fraction(n, m, _)) = heap.pop().unwrap();
vec![n, m]
}
}