Medium

题目描述

给你一个按递增顺序排序的数组 arr，它包含 1 和若干质数。数组中的所有整数互不相同。同时给你一个整数 k。

对于每一对满足 0 <= i < j < arr.length 的 i 和 j，我们可以得到分数 arr[i] / arr[j]。

返回第 k 小的分数，用长度为 2 的整数数组 [arr[i], 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 * 10^4
  • arr[0] == 1
  • 当 i > 0 时，arr[i] 是质数
  • arr 中的所有数字互不相同且按严格递增顺序排序
  • 1 <= k <= arr.length * (arr.length - 1) / 2

进阶： 你能设计一个时间复杂度小于 O(n²) 的算法吗？

解题思路

这道题要找第K小的分数，有以下几种思路：

方法一：优先队列（最小堆）

最直观的想法是使用最小堆。我们可以将所有可能的分数放入优先队列，然后取出第k小的。但是直接放入所有分数会造成空间浪费，更好的做法是：

  1. 初始时将每行的第一个分数 arr[i]/arr[n-1] 放入堆中
  2. 每次取出最小值后，将该分数对应行的下一个分数加入堆中
  3. 重复k次即可得到答案

方法二：二分查找 + 双指针（推荐）

更高效的方法是使用二分查找。我们二分查找一个目标值x，然后统计有多少个分数小于等于x：

  1. 二分查找的范围是 [0, 1]
  2. 对于每个mid值，使用双指针统计小于等于mid的分数个数
  3. 如果个数大于等于k，说明第k小的分数小于等于mid
  4. 在统计过程中记录最接近mid且小于等于mid的最大分数

这种方法的时间复杂度可以达到 O(n log(max_val))，比O(n²)更优。

代码实现

class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
        int n = arr.size();
        double left = 0, right = 1;
        
        while (left < right) {
            double mid = left + (right - left) / 2;
            int count = 0, p = 0, q = 1;
            
            // 使用双指针统计小于等于mid的分数个数
            for (int i = 0, j = n - 1; i < n; i++) {
                while (j > i && arr[i] > mid * arr[j]) {
                    j--;
                }
                count += j - i;
                
                // 记录最接近mid的分数
                if (j > i && arr[i] * q > arr[j] * p) {
                    p = arr[i];
                    q = arr[j];
                }
            }
            
            if (count == k) {
                return {p, q};
            } else if (count < k) {
                left = mid;
            } else {
                right = mid;
            }
        }
        
        return {};
    }
};

class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        n = len(arr)
        left, right = 0, 1
        
        while left < right:
            mid = (left + right) / 2
            count = 0
            p, q = 0, 1
            
            # 使用双指针统计小于等于mid的分数个数
            j = n - 1
            for i in range(n):
                while j > i and arr[i] > mid * arr[j]:
                    j -= 1
                count += j - i
                
                # 记录最接近mid的分数
                if j > i and arr[i] * q > arr[j] * p:
                    p, q = arr[i], arr[j]
            
            if count == k:
                return [p, q]
            elif count < k:
                left = mid
            else:
                right = mid
        
        return []

public class Solution {
    public int[] KthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.Length;
        double left = 0, right = 1;
        
        while (left < right) {
            double mid = left + (right - left) / 2;
            int count = 0, p = 0, q = 1;
            
            // 使用双指针统计小于等于mid的分数个数
            for (int i = 0, j = n - 1; i < n; i++) {
                while (j > i && arr[i] > mid * arr[j]) {
                    j--;
                }
                count += j - i;
                
                // 记录最接近mid的分数
                if (j > i && arr[i] * q > arr[j] * p) {
                    p = arr[i];
                    q = arr[j];
                }
            }
            
            if (count == k) {
                return new int[] {p, q};
            } else if (count < k) {
                left = mid;
            } else {
                right = mid;
            }
        }
        
        return new int[0];
    }
}

var kthSmallestPrimeFraction = function(arr, k) {
    const fractions = [];
    
    for (let i = 0; i < arr.length; i++) {
        for (let j = i + 1; j < arr.length; j++) {
            fractions.push([arr[i] / arr[j], arr[i], arr[j]]);
        }
    }
    
    fractions.sort((a, b) => a[0] - b[0]);
    
    return [fractions[k - 1][1], fractions[k - 1][2]];
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

方法时间复杂度空间复杂度
优先队列O(k log n)O(n)
二分查找 + 双指针O(n log(max_val))O(1)

其中 max_val 是数组中的最大值。二分查找方法在实际应用中通常更优，特别是当k较大时。

相关题目