宫水三叶的刷题日记

V1

2022/09/14阅读:20主题:前端之巅同款

【面试高频题】难度 2.5/5,多解法经典面试笔试题

题目描述

这是 LeetCode 上的 786. 第 K 个最小的素数分数 ,难度为 中等

Tag : 「优先队列(堆)」、「多路归并」、「二分」、「双指针」

给你一个按递增顺序排序的数组 arr 和一个整数 k

数组 arr 和若干 素数  组成,且其中所有整数互不相同。

对于每对满足 ,可以得到分数

那么第   个最小的分数是多少呢?  以长度为 的整数数组返回你的答案, 这里   且 

示例 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]

提示:

  • 是一个 素数 ,
  • 中的所有数字 互不相同 ,且按严格递增排序

优先队列(堆)

数据范围只有 ,直接扫描所有点对的计算量不超过

因此我们可以使用「扫描点对」+「优先队列(堆)」的做法,使用二元组 进行存储,构建大小为 的大根堆。

根据「堆内元素多少」和「当前计算值与堆顶元素的大小关系」决定入堆行为:

  • 若堆内元素不足 个,直接将当前二元组进行入堆;
  • 若堆内元素已达 个,根据「当前计算值 与堆顶元素 的大小关系」进行分情况讨论:
    • 如果当前计算值比堆顶元素大,那么当前元素不可能是第 小的值,直接丢弃;
    • 如果当前计算值比堆顶元素小,那么堆顶元素不可能是第 小的值,使用当前计算值置换掉堆顶元素。

代码:

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.length;
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->Double.compare(b[0]*1.0/b[1],a[0]*1.0/a[1]));
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                double t = arr[i] * 1.0 / arr[j];
                if (q.size() < k || q.peek()[0] * 1.0 / q.peek()[1] > t) {
                    if (q.size() == k) q.poll();
                    q.add(new int[]{arr[i], arr[j]});
                }
            }
        }
        return q.poll();
    }
}
  • 时间复杂度:扫描所有的点对复杂度为 ;将二元组入堆和出堆的复杂度为 。整体复杂度为
  • 空间复杂度:

多路归并

在解法一中,我们没有利用「数组内元素严格单调递增」的特性。

由于题目规定所有的点对 必须满足 ,即给定 后,其所能构建的分数个数为 个,而这 个分数值满足严格单调递增:

问题等价于我们从 个(下标 作为分母的话,不存在任何分数)有序序列中找到第 小的数值。这 个序列分别为:

  • ...

问题彻底切换为「多路归并」问题,我们使用「优先队列(堆)」来维护多个有序序列的当前头部的最小值即可。

代码:

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.length;
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->{
            double i1 = arr[a[0]] * 1.0 / arr[a[1]], i2 = arr[b[0]] * 1.0 / arr[b[1]];
            return Double.compare(i1, i2);
        });
        for (int i = 1; i < n; i++) q.add(new int[]{0, i});
        while (k-- > 1) {
            int[] poll = q.poll();
            int i = poll[0], j = poll[1];
            if (i + 1 < j) q.add(new int[]{i + 1, j});
        }
        int[] poll = q.poll();
        return new int[]{arr[poll[0]], arr[poll[1]]};
    }
}
  • 时间复杂度:起始将 个序列的头部元素放入堆中,复杂度为 ;然后重复 次操作得到第 小的值,复杂度为 。整体复杂度为
  • 空间复杂度:

二分 + 双指针

进一步,利用 递增,且每个点对 满足 ,我们可以确定 对应的分数 必然落在 范围内。

假设最终答案 ,那么以 为分割点的数轴(该数轴上的点为 所能构造的分数值)上具有「二段性」:

  • 小于等于 的值满足:其左边分数值个数小于 个;
  • 大于 的值不满足:其左边分数值个数小于 个(即至少有 个)。

而当确定 时,利用 有序,我们可以通过「双指针」快速得知,满足 的分子位置在哪(找到最近一个满足 的位置)。

另外,我们可以在每次 check 的同时,记录下相应的

代码:

class Solution {
    double eps = 1e-8;
    int[] arr;
    int n, a, b;
    public int[] kthSmallestPrimeFraction(int[] _arr, int k) {
        arr = _arr;
        n = arr.length;
        double l = 0, r = 1;
        while (r - l > eps) {
            double mid = (l + r) / 2;
            if (check(mid) >= k) r = mid;
            else l = mid;
        }
        return new int[]{a, b};
    }
    int check(double x){
        int ans = 0;
        for (int i = 0, j = 1; j < n; j++) {
            while (arr[i + 1] * 1.0 / arr[j] <= x) i++;
            if (arr[i] * 1.0 / arr[j] <= x) ans += i + 1;
            if (Math.abs(arr[i] * 1.0 / arr[j] - x) < eps) {
                a = arr[i]; b = arr[j];
            }
        }
        return ans;
    }
}
  • 时间复杂度:二分次数取决于精度,精度为 ,二分复杂度为 check 的复杂度为 。整体复杂度为
  • 空间复杂度:

最后

这是我们「刷穿 LeetCode」系列文章的第 No.786 篇,系列开始于 2021/01/01,截止于起始日 LeetCode 上共有 1916 道题目,部分是有锁题,我们将先把所有不带锁的题目刷完。

在这个系列文章里面,除了讲解解题思路以外,还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码,我建立了相关的仓库:https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里,你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

分类:

后端

标签:

后端

作者介绍

宫水三叶的刷题日记
V1