Задача: 786. K-th Smallest Prime Fraction
Сложность: medium

Вам дан отсортированный массив целых чисел 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.

👨‍💻 Алгоритм:

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

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

3⃣Извлеките индексы числителя и знаменателя из верхнего элемента pq, верните массив [arr[числитель], arr[знаменатель]], соответствующий k-й наименьшей дроби.

😎 Решение:

class Solution {
    func kthSmallestPrimeFraction(_ arr: [Int], _ k: Int) -> [Int] {
        var pq = PriorityQueue<(Double, Int, Int)>()
        
        for i in 0..<arr.count - 1 {
            pq.push((Double(arr[i]) / Double(arr.last!), i, arr.count - 1))
        }
        
        for _ in 0..<k - 1 {
            let cur = pq.pop()!
            if cur.2 > cur.1 {
                pq.push((Double(arr[cur.1]) / Double(arr[cur.2 - 1]), cur.1, cur.2 - 1))
            }
        }
        
        let result = pq.pop()!
        return [arr[result.1], arr[result.2]]
    }
}

struct PriorityQueue<T: Comparable> {
    private var heap: [T] = []
    
    mutating func push(_ element: T) {
        heap.append(element)
        heapify(from: heap.count - 1)
    }
    
    mutating func pop() -> T? {
        guard !heap.isEmpty else { return nil }
        let root = heap[0]
        heap[0] = heap.removeLast()
        heapify(from: 0)
        return root
    }
    
    private mutating func heapify(from index: Int) {
        var idx = index
        let child = heap[idx]
        var parentIdx = (idx - 1) / 2
        
        while idx > 0 && heap[parentIdx] > child {
            heap[idx] = heap[parentIdx]
            idx = parentIdx
            parentIdx = (idx - 1) / 2
        }
        
        heap[idx] = child
        var parentIndex = 0
        
        while true {
            let leftChild = 2 * parentIndex + 1
            let rightChild = 2 * parentIndex + 2
            var swapIndex: Int?
            
            if leftChild < heap.count && heap[leftChild] < heap[parentIndex] {
                swapIndex = leftChild
            }
            if rightChild < heap.count && heap[rightChild] < (swapIndex != nil ? heap[swapIndex!] : heap[parentIndex]) {
                swapIndex = rightChild
            }
            guard let idx = swapIndex else { return }
            
            heap.swapAt(parentIndex, idx)
            parentIndex = idx
        }
    }
}

Ставь 👍 и забирай 📚 Базу знаний