列表

详情

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

 

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

 

提示：

相似题目

有序矩阵中第 K 小的元素

乘法表中第k小的数

找出第 K 小的数对距离

原站题解

去查看

上次编辑到这里，代码来自缓存 点击恢复默认模板
class Solution { public: vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) { } };

python3 解法, 执行用时: 80 ms, 内存消耗: 15 MB, 提交时间: 2022-11-26 17:52:48 

class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        n = len(arr)
        left, right = 0.0, 1.0

        while True:
            mid = (left + right) / 2
            i, count = -1, 0
            # 记录最大的分数
            x, y = 0, 1
            
            for j in range(1, n):
                while arr[i + 1] / arr[j] < mid:
                    i += 1
                    if arr[i] * y > arr[j] * x:
                        x, y = arr[i], arr[j]
                count += i + 1

            if count == k:
                return [x, y]
            
            if count < k:
                left = mid
            else:
                right = mid

javascript 解法, 执行用时: 60 ms, 内存消耗: 41.6 MB, 提交时间: 2022-11-26 17:52:34 

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
var kthSmallestPrimeFraction = function(arr, k) {
    const n = arr.length;
    let left = 0.0, right = 1.0;
    while (true) {
        const mid = (left + right) / 2;
        let i = -1, count = 0;
        // 记录最大的分数
        let x = 0, y = 1;
        
        for (let j = 1; j < n; ++j) {
            while (arr[i + 1] / arr[j] < mid) {
                ++i;
                if (arr[i] * y > arr[j] * x) {
                    x = arr[i];
                    y = arr[j];
                }
            }
            count += i + 1;
        }

        if (count === k) {
            return [x, y];
        }
        if (count < k) {
            left = mid;
        } else {
            right = mid;
        }
    }
};

golang 解法, 执行用时: 4 ms, 内存消耗: 2.3 MB, 提交时间: 2022-11-26 17:52:18 

func kthSmallestPrimeFraction(arr []int, k int) []int {
    n := len(arr)
    left, right := 0., 1.
    for {
        mid := (left + right) / 2
        i, count := -1, 0
        // 记录最大的分数
        x, y := 0, 1

        for j := 1; j < n; j++ {
            for float64(arr[i+1])/float64(arr[j]) < mid {
                i++
                if arr[i]*y > arr[j]*x {
                    x, y = arr[i], arr[j]
                }
            }
            count += i + 1
        }

        if count == k {
            return []int{x, y}
        }
        if count < k {
            left = mid
        } else {
            right = mid
        }
    }
}

golang 解法, 执行用时: 240 ms, 内存消耗: 6.7 MB, 提交时间: 2022-11-26 17:51:59 

func kthSmallestPrimeFraction(arr []int, k int) []int {
    n := len(arr)
    h := make(hp, n-1)
    for j := 1; j < n; j++ {
        h[j-1] = frac{arr[0], arr[j], 0, j}
    }
    heap.Init(&h)
    for loop := k - 1; loop > 0; loop-- {
        f := heap.Pop(&h).(frac)
        if f.i+1 < f.j {
            heap.Push(&h, frac{arr[f.i+1], f.y, f.i + 1, f.j})
        }
    }
    return []int{h[0].x, h[0].y}
}

type frac struct{ x, y, i, j int }
type hp []frac
func (h hp) Len() int            { return len(h) }
func (h hp) Less(i, j int) bool  { return h[i].x*h[j].y < h[i].y*h[j].x }
func (h hp) Swap(i, j int)       { h[i], h[j] = h[j], h[i] }
func (h *hp) Push(v interface{}) { *h = append(*h, v.(frac)) }
func (h *hp) Pop() interface{}   { a := *h; v := a[len(a)-1]; *h = a[:len(a)-1]; return v }

python3 解法, 执行用时: 3144 ms, 内存消耗: 15.3 MB, 提交时间: 2022-11-26 17:51:44 

class Frac:
    def __init__(self, idx: int, idy: int, x: int, y: int) -> None:
        self.idx = idx
        self.idy = idy
        self.x = x
        self.y = y

    def __lt__(self, other: "Frac") -> bool:
        return self.x * other.y < self.y * other.x


class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        n = len(arr)
        q = [Frac(0, i, arr[0], arr[i]) for i in range(1, n)]
        heapq.heapify(q)

        for _ in range(k - 1):
            frac = heapq.heappop(q)
            i, j = frac.idx, frac.idy
            if i + 1 < j:
                heapq.heappush(q, Frac(i + 1, j, arr[i + 1], arr[j]))
        
        return [q[0].x, q[0].y]

javascript 解法, 执行用时: 1780 ms, 内存消耗: 100.9 MB, 提交时间: 2022-11-26 17:51:27 

/**
 * @param {number[]} arr
 * @param {number} k
 * @return {number[]}
 */
var kthSmallestPrimeFraction = function(arr, k) {
    const n = arr.length;
    const frac = [];
    for (let i = 0; i < n; ++i) {
        for (let j = i + 1; j < n; ++j) {
            frac.push([arr[i], arr[j]]);
        }
    }
    frac.sort((x, y) => x[0] * y[1] - y[0] * x[1]);
    return frac[k - 1];
};

golang 解法, 执行用时: 512 ms, 内存消耗: 23.7 MB, 提交时间: 2022-11-26 17:51:15 

func kthSmallestPrimeFraction(arr []int, k int) []int {
    n := len(arr)
    type pair struct{ x, y int }
    frac := make([]pair, 0, n*(n-1)/2)
    for i, x := range arr {
        for _, y := range arr[i+1:] {
            frac = append(frac, pair{x, y})
        }
    }
    sort.Slice(frac, func(i, j int) bool {
        a, b := frac[i], frac[j]
        return a.x*b.y < a.y*b.x
    })
    return []int{frac[k-1].x, frac[k-1].y}
}

python3 解法, 执行用时: 6340 ms, 内存消耗: 77.8 MB, 提交时间: 2022-11-26 17:50:59 

class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        def cmp(x: Tuple[int, int], y: Tuple[int, int]) -> int:
            return -1 if x[0] * y[1] < x[1] * y[0] else 1
        
        n = len(arr)
        frac = list()
        for i in range(n):
            for j in range(i + 1, n):
                frac.append((arr[i], arr[j]))
        
        frac.sort(key=cmp_to_key(cmp))
        return list(frac[k - 1])

上一题

© 2024 leetcode.cn