LeetCode每日一题之786. 第 K 个最小的素数分数

本文主要是介绍LeetCode每日一题之786. 第 K 个最小的素数分数，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

786. 第 K 个最小的素数分数

题目链接地址

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

提示：

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

题解：

我们采用优先队列 + 双指针的方法进行求解该问题

思路如下：

我们定义一个优先队列，从小到大存储分子/分母的结果
然后定义两个指针，left指针记录分子在arr数组中的下标，right指针记录分母在arr数组中的下标
定义两个map，记录队列中的值与实际arr的分子分母位置的映射关系
我们首先将第一个最小的值放入优先队列中，并将其分子分母的位置映射存储到两个map中去
最后，定义一个计数器index，当index == k，说明此时已经到达第k小个值，则直接弹出队列中的首元素即为第k小的值

注意：

为了防止优先队列中放入重复的值，这里需要添加一个if判断，看他是否在map中存储过！！！

以arr = [1,2,3,5], k = 3为例：

在这里插入图片描述

代码实现：

//优先队列 + 双指针法
public int[] kthSmallestPrimeFraction(int[] arr, int k) {int n = arr.length;//定义一个优先队列：从小到大存储分子/分母的结果PriorityQueue<Double> queue = new PriorityQueue<>();//显然，我们知道arr数组是默认严格递增排序的，则刚开始最小值的位置（分子:0,分母:n - 1）int left = 0;int right = n - 1;//记录队列中的值与实际arr的分子分母位置的映射关系Map<Double, Integer> lMap = new HashMap<>();Map<Double, Integer> rMap = new HashMap<>();//我们首先将第一个最小的值放入优先队列中，并将其分子分母的位置映射存储到两个map中去Double num = (double)arr[left] / arr[right];queue.add(num);lMap.put(num,left);rMap.put(num,right);//定义一个计数器，当index == k,直接弹出队列中的首元素即为第k小的值int index = 1;while (index < k) {num = queue.poll();Integer l = lMap.get(num);Integer r = rMap.get(num);//获取当前值的左边的值Double val = (double)arr[l] / arr[r - 1];//为了防止放入重复的值，这里需要添加一个if判断，下面也一样if (!lMap.containsKey(val)) {queue.add(val);lMap.put(val,l);rMap.put(val,r - 1);}//获取当前值的下边的值val = (double) arr[l + 1] / arr[r];if (!lMap.containsKey(val)) {queue.add(val);lMap.put(val,l + 1);rMap.put(val,r);}++index;}//最后弹出队列首元素对应在两个map中的位置值，即为结果集return new int[]{arr[lMap.get(queue.peek())],arr[rMap.get(queue.peek())]};
}