LeetCode 786. 第 K 个最小的质数分数

Categories:

题目描述
思路分析
1. 解法一：最小堆（推荐）
相似题目

题目描述

✅ 786. 第 K 个最小的质数分数

思路分析

解法一：最小堆（推荐）

核心思路：

将每个分子 arr[i] 与最大分母 arr[n-1] 组成初始分数入堆。

每次弹出当前最小分数 (i, j)，并将 (i, j-1) 入堆。

弹出第 k 次即为答案。

复杂度分析：

时间复杂度：O(k log n)，其中 n 为数组长度。

空间复杂度：O(n)，堆中最多保存 n 个元素。

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        int n = arr.length;
        PriorityQueue<int[]> pq = new PriorityQueue<>(
                (a, b) -> Long.compare(
                        (long) arr[a[0]] * arr[b[1]],
                        (long) arr[b[0]] * arr[a[1]]
                )
        );

        for (int i = 0; i < n - 1; i++) {
            pq.offer(new int[]{i, n - 1});
        }

        // 弹出 k-1 次
        for (int t = 1; t < k; t++) {
            int[] cur = pq.poll();
            int i = cur[0];
            int j = cur[1];
            if (j - 1 > i) {
                pq.offer(new int[]{i, j - 1});
            }
        }

        int[] ans = pq.peek();
        return new int[]{arr[ans[0]], arr[ans[1]]};
    }
}

import "container/heap"

func kthSmallestPrimeFraction(arr []int, k int) []int {
	n := len(arr)
	h := &FracHeap{arr: arr}
	heap.Init(h)

	for i := 0; i < n-1; i++ {
		heap.Push(h, Pair{i: i, j: n - 1})
	}

	for t := 1; t < k; t++ {
		cur := heap.Pop(h).(Pair)
		if cur.j-1 > cur.i {
			heap.Push(h, Pair{i: cur.i, j: cur.j - 1})
		}
	}

	ans := heap.Pop(h).(Pair)
	return []int{arr[ans.i], arr[ans.j]}
}

type Pair struct {
	i int
	j int
}

type FracHeap struct {
	data []Pair
	arr  []int
}

func (h FracHeap) Len() int { return len(h.data) }
func (h FracHeap) Less(i, j int) bool {
	a := h.data[i]
	b := h.data[j]
	return h.arr[a.i]*h.arr[b.j] < h.arr[b.i]*h.arr[a.j]
}
func (h FracHeap) Swap(i, j int) { h.data[i], h.data[j] = h.data[j], h.data[i] }
func (h *FracHeap) Push(x any)   { h.data = append(h.data, x.(Pair)) }
func (h *FracHeap) Pop() any {
	old := h.data
	n := len(old)
	val := old[n-1]
	h.data = old[:n-1]
	return val
}

相似题目

题目	难度	考察点
373. 查找和最小的 K 对数字	中等	堆
378. 有序矩阵中第 K 小的元素	中等	堆
719. 找出第 K 小的数对距离	困难	二分
658. 找到 K 个最接近的元素	中等	二分 + 双指针
215. 数组中的第 K 个最大元素	中等	堆 / 快速选择

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2023/46989450