精进Leetcode每日一题-1129

这是我参与11月更文挑战的第27天，活动详情查看：2021最后一次更文挑战

目标：拼搏30天，拿到11月的Leetcode 月度勋章。今天是第 29 天。

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] 。

分析：

遍历数组，将所有分数存储下来并使用优先队列存储（需要自定义排序函数），然后出队k次，

存储分数时，如果直接存储小数会影响效率，直接存储分子和分母即可。

​

ba​<dc​=>ad<cb
优化：

因为数组是有序的，当分母确定时，会构成一个递增序列,因此会生成n个递增序列

例如：arr=[1,2,3,5,7]

所有元素中最小的元素必然是​

arr[n−1]arr[0]​arr[n−1]arr[0],我们将​

arr[i]arr[0]​,(i∈[0,n))arr[i]arr[0],(i∈[0,n))全部入队。

如上示例，最小的元素1/7,那下一个元素要么是它上面的第一个元素，要么是它右边的第一个元素，我们将它右边的第一个元素入队(第一列已经全部在队列中)，并重复该过程k次并出队，此时队头元素便是第k小元素。

    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        PriorityQueue<int[]> pq=new PriorityQueue<>((o1, o2) -> o1[0]* o2[1]-o1[1]* o2[0]);
        for(int i=0;i<arr.length;i++){
            for(int j=i+1;j<arr.length;j++){
                pq.add(new int[]{arr[i],arr[j]});
            }
        }
        for(int i=1;i<k && !pq.isEmpty();i++){
            pq.poll();
        }
        if(pq.isEmpty()){
            return new int[]{};
        }
        return pq.poll();
    }

复制代码

• 时间复杂度：O(Nlogn)，
• 空间复杂度：O(N)。

提交排名