• LeetCode每日一题(786. K-th Smallest Prime Fraction)


    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]
        }
    }
    
    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
  • 相关阅读:
    QT-输入输出
    SHELL中的数组及其相关操作
    MDC轻量化日志链路跟踪的若干种应用场景
    每日一练 | 网络工程师软考真题Day40
    uniapp自定义顶部导航栏
    大数据Flink(五十四):Flink用武之地
    Halcon实例转OpenCvSharp(C# OpenCV)实现--瓶口缺陷检测(附源码)
    Swift中的协议
    基础shell小技巧004
    推荐一个react拖拽排序的库,@dnd-kit
  • 原文地址:https://blog.csdn.net/wangjun861205/article/details/126778075