LeetCode——786. 第 K 个最小的素数分数（Java）

本文主要是介绍LeetCode——786. 第 K 个最小的素数分数（Java），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

题目描述

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

题解思路

返回第k个大小的分数，这里直接用List把所有可能的情况全部记录下来，返回第k个结果即可

当然每次返回第k个结果的题目都可以用最小堆或者优先队列的方式解答，有想法的可以去尝试一下

正确代码

    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.length;

        List<int[]> fraction = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                fraction.add(new int[]{arr[i], arr[j]});
            }
        }
        fraction.sort((x, y) -> x[0] * y[1] - y[0] * x[1]);
        return fraction.get(k - 1);
    }

总结

一般我们提到堆的时候往往会和优先队列关联起来，因为优先队列可以用堆来实现

所以可以采用优先队列来实现的都可以用堆来做，它的用途也十分广泛

比如构造哈夫曼编码、一些任务调度算法、合并N个有序的文件、排序、找中位数或者找最大的k个数

如果文章存在问题或者有更好的题解，欢迎在评论区斧正和评论，各自努力，最高处见

这篇关于LeetCode——786. 第 K 个最小的素数分数（Java）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！