786. K-th Smallest Prime Fraction

leetcode medium

#array#csharp#heap#leetcode#math#medium#queue#sort

Task

Вам дан отсортированный массив целых чисел arr, содержащий 1 и простые числа, где все элементы массива arr уникальны. Также дано целое число k.

Для каждого i и j, где 0 <= i < j < arr.length, мы рассматриваем дробь arr[i] / arr[j].

Верните k-ую наименьшую дробь из рассмотренных. Верните ответ в виде массива из двух целых чисел размера 2, где answer[0] == arr[i] и answer[1] == arr[j].

Пример:

Input: arr = [1,2,3,5], k = 3

Output: [2,5]

Explanation: The fractions to be considered in sorted order are:

1/5, 1/3, 2/5, 1/2, 3/5, and 2/3.

The third fraction is 2/5.

C# solution

matched/original

using System;
using System.Collections.Generic;
public class Solution {
    public int[] KthSmallestPrimeFraction(int[] arr, int k) {
        var pq = new PriorityQueue<(double Fraction, int[] Indices), double>();
        for (int i = 0; i < arr.Length - 1; i++) {
            pq.Enqueue((arr[i] / (double)arr[arr.Length - 1], new int[] { i, arr.Length - 1 }), arr[i] / (double)arr[arr.Length - 1]);
        }
        for (int i = 0; i < k - 1; i++) {
            var (fraction, indices) = pq.Dequeue();
            var numeratorIndex = indices[0];
            var denominatorIndex = indices[1] - 1;
            if (denominatorIndex > numeratorIndex) {
                pq.Enqueue((arr[numeratorIndex] / (double)arr[denominatorIndex], new int[] { numeratorIndex, denominatorIndex }), arr[numeratorIndex] / (double)arr[denominatorIndex]);
            }
        }
        var result = pq.Dequeue();
        return new int[] { arr[result.Indices[0]], arr[result.Indices[1]] };
    }
}

C++ solution

auto-draft, review before submit

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& KthSmallestPrimeFraction(vector<int>& arr, int k) {
        var pq = new PriorityQueue<(double Fraction, vector<int>& Indices), double>();
        for (int i = 0; i < arr.size() - 1; i++) {
            pq.Enqueue((arr[i] / (double)arr[arr.size() - 1], new int[] { i, arr.size() - 1 }), arr[i] / (double)arr[arr.size() - 1]);
        }
        for (int i = 0; i < k - 1; i++) {
            var (fraction, indices) = pq.Dequeue();
            var numeratorIndex = indices[0];
            var denominatorIndex = indices[1] - 1;
            if (denominatorIndex > numeratorIndex) {
                pq.Enqueue((arr[numeratorIndex] / (double)arr[denominatorIndex], new int[] { numeratorIndex, denominatorIndex }), arr[numeratorIndex] / (double)arr[denominatorIndex]);
            }
        }
        var result = pq.Dequeue();
        return new int[] { arr[result.Indices[0]], arr[result.Indices[1]] };
    }
}

Java solution

matched/original

import java.util.PriorityQueue;

class Solution {
    public int[] kthSmallestPrimeFraction(int[] arr, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> Double.compare((double)arr[a[0]] / arr[a[1]], (double)arr[b[0]] / arr[b[1]]));
        
        for (int i = 0; i < arr.length - 1; i++) {
            pq.offer(new int[]{i, arr.length - 1});
        }
        
        for (int i = 0; i < k - 1; i++) {
            int[] cur = pq.poll();
            if (cur[1] - 1 > cur[0]) {
                pq.offer(new int[]{cur[0], cur[1] - 1});
            }
        }
        
        int[] result = pq.poll();
        return new int[]{arr[result[0]], arr[result[1]]};
    }
}

JavaScript solution

matched/original

class Solution {
    kthSmallestPrimeFraction(arr, k) {
        const pq = new MinPriorityQueue({ compare: (a, b) => a.fraction - b.fraction });

        for (let i = 0; i < arr.length - 1; i++) {
            pq.enqueue({
                fraction: arr[i] / arr[arr.length - 1],
                indices: [i, arr.length - 1]
            });
        }

        for (let i = 0; i < k - 1; i++) {
            const { indices } = pq.dequeue();
            const [numeratorIndex, denominatorIndex] = indices;
            if (denominatorIndex - 1 > numeratorIndex) {
                pq.enqueue({
                    fraction: arr[numeratorIndex] / arr[denominatorIndex - 1],
                    indices: [numeratorIndex, denominatorIndex - 1]
                });
            }
        }

        const result = pq.dequeue().indices;
        return [arr[result[0]], arr[result[1]]];
    }
}

Go solution

matched/original

package main

import (
    "container/heap"
)

type Fraction struct {
    value   float64
    indices [2]int
}

type PriorityQueue []Fraction

func (pq PriorityQueue) Len() int { return len(pq) }

func (pq PriorityQueue) Less(i, j int) bool {
    return pq[i].value < pq[j].value
}

func (pq PriorityQueue) Swap(i, j int) {
    pq[i], pq[j] = pq[j], pq[i]
}

func (pq *PriorityQueue) Push(x interface{}) {
    *pq = append(*pq, x.(Fraction))
}

func (pq *PriorityQueue) Pop() interface{} {
    old := *pq
    n := len(old)
    item := old[n-1]
    *pq = old[0 : n-1]
    return item
}

func kthSmallestPrimeFraction(arr []int, k int) []int {
    pq := &PriorityQueue{}
    heap.Init(pq)

    for i := 0; i < len(arr)-1; i++ {
        heap.Push(pq, Fraction{float64(arr[i]) / float64(arr[len(arr)-1]), [2]int{i, len(arr) - 1}})
    }

    for i := 0; i < k-1; i++ {
        cur := heap.Pop(pq).(Fraction)
        if cur.indices[1]-1 > cur.indices[0] {
            heap.Push(pq, Fraction{float64(arr[cur.indices[0]]) / float64(arr[cur.indices[1]-1]), [2]int{cur.indices[0], cur.indices[1] - 1}})
        }
    }

    result := heap.Pop(pq).(Fraction)
    return []int{arr[result.indices[0]], arr[result.indices[1]]}
}

Explanation

Algorithm

Инициализируйте пустую приоритетную очередь pq для хранения пар дробей и соответствующих им индексов. Итеративно пройдите по входному массиву arr, используя переменную цикла i. Для каждого элемента arr[i] вычислите дробь, образованную делением его на наибольший элемент в массиве (arr[arr.size() - 1]). Поместите пару, состоящую из отрицательного значения дроби (-1.0 * arr[i] / arr[arr.size() - 1]) и соответствующих индексов (i для числителя и arr.size() - 1 для знаменателя), в приоритетную очередь pq. Приоритетная очередь pq теперь содержит все дроби, образованные делением каждого элемента на наибольший элемент в массиве, отсортированные в порядке возрастания значений дробей.

Повторите следующие шаги k - 1 раз: удалите верхний элемент (наименьшую дробь) из приоритетной очереди pq и сохраните его индексы в переменной cur. Уменьшите индекс знаменателя (cur[1]--). Вычислите новую дробь, образованную делением числителя в cur[0] на уменьшенный знаменатель (arr[cur[1]]). Поместите новое значение дроби (-1.0 * arr[cur[0]] / arr[cur[1]]) и соответствующие индексы (cur[0] для числителя и cur[1] для знаменателя) в приоритетную очередь pq. После k - 1 итераций верхний элемент приоритетной очереди pq будет k-й наименьшей дробью.

Извлеките индексы числителя и знаменателя из верхнего элемента приоритетной очереди и сохраните их в result. Верните массив, содержащий значения числителя (arr[result[0]]) и знаменателя (arr[result[1]]), соответствующие k-й наименьшей дроби.

😎