X

LEETCODE 786. K-th Smallest Prime Fraction 解题思路分析

题目大意:

第 K 个最小的素数分数

一个已排序好的表 A,其包含 1 和其他一些素数.  当列表中的每一个 p<q 时,我们可以构造一个分数 p/q 。

那么第 k 个最小的分数是多少呢?  以整数数组的形式返回你的答案, 这里 answer[0] = p 且 answer[1] = q.

示例:
输入: A = [1, 2, 3, 5], K = 3
输出: [2, 5]
解释:
已构造好的分数,排序后如下所示:
1/5, 1/3, 2/5, 1/2, 3/5, 2/3.
很明显第三个最小的分数是 2/5.
输入: A = [1, 7], K = 1
输出: [1, 7]

注意:

  • A 的取值范围在 2 — 2000.
  • 每个 A[i] 的值在 1 —30000.
  • K 取值范围为 1 —A.length * (A.length – 1) / 2

如果想查看本题目是哪家公司的面试题,请参考以下免费链接: https://leetcode.jp/problemdetail.php?id=786

解题思路分析:

题目给出的数组已经按照升序方式排列好,因此我们可以快速的得知,数组中第一个数与最后一个数组成的分数一定是最小的,而第二小的可能是第一个数与倒数第二个数组成的分数N1,或者是第二个数与最后一个数组成的分数N2,到这一步我们就无法再继续判断下去了。因此,解题时,我们可以建立一个PriorityQueue,按照大小顺序来存储所有分数,然后取出第K个元素就是第K小的分数。

不过这样做需要将所有分数都列举出来,大概率会超时。所以我们可以考虑先将所有数字与第一个数字组成的分数存入Queue。接下来从Queue中取出第一个元素,它一定最小的那个(首元素与尾元素组成的分数),然后我们将这个元素的分子向后移动一位,即利用第二个元素与尾元素组成一个新的分数,这个分数是稍微大于最小分数的一个数字,也是上文提到过的N2,我们将它插入到Queue中,这时Queue中一定存在N1和N2两个相对最小的分数,我们再从Queue中取出最小的一个,重复上述过程,直到第K次取出的元素即是本题的解。

实现代码:

public int[] kthSmallestPrimeFraction(int[] A, int K) {
    // 排序用的Queue,
    // Queue中存储的是分子index,分母index,以及分数的值
    PriorityQueue<double[]> q
        =new PriorityQueue<>((a,b)->a[2]-b[2]>0?1:-1);
    // 将所有数数字与首元素组成的分数存入Queue
    for(int i=1;i<A.length;i++){
        q.offer(new double[]{0,i,(double)A[0]/A[i]});
    }
    // 返回结果
    int[] res=new int[2];
    // 循环K次,每次从Queue中取出最小元素
    for(int i=1;i<=K;i++){
        // 取出最小元素
        double[] arr=q.poll();
        // 如果当前是第K次,
        if(i==K){
            // 将当前元素的分子与分母下标赋值到返回结果
            res[0]=A[(int)arr[0]];
            res[1]=A[(int)arr[1]];
            break;
        }
        // 将分子对应数组中的下标变大一位
        arr[0]++;
        // 重新计算当前分数的值
        arr[2]=(double)A[(int)arr[0]]/A[(int)arr[1]];
        // 将当前分数加入Queue
        q.offer(arr);
    }
    return res;
}

本题解法执行时间为821ms。

Runtime: 821 ms, faster than 23.97% of Java online submissions for K-th Smallest Prime Fraction.

Memory Usage: 41.6 MB, less than 33.33% of Java online submissions for K-th Smallest Prime Fraction.

本网站文章均为原创内容,并可随意转载,但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论,本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言,并会在第一时间对您的留言进行回复!欢迎交流!
本文链接: http://leetcode.jp/leetcode-786-k-th-smallest-prime-fraction-解题思路分析/
Categories: leetcode
kwantong: