thảo luận Leetcode mỗi ngày

class Solution {

    /**
     * @param Integer[] $arr
     * @param Integer $k
     * @return Integer[]
     */
    function kthSmallestPrimeFraction($arr, $k) {
        $length = count($arr);
        if ($lenght == 2) {
            return $arr;
        }

        // loop arr to create new array of fractions
        $fracs = [];
        for ($i=0; $i<$length-1; $i++) {
            for ($j=$i+1; $j<$length; $j++) {
                $key = $arr[$i].",".$arr[$j]; // use arr[$i],arr[$j] as key
                $fracs[$key] = $arr[$i]/$arr[$j];
            }
        }

        asort($fracs); // sort values asc, don't change the index
        $search = 1;
        foreach($fracs as $key => $frac) {
            if ($search == $k) {
                return explode(",", $key); // return the key
            }

            $search++;
        }
    }
}

import heapq
class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        pq = []
        lastIdx = len(arr) - 1
        for i in range(lastIdx):
            heapq.heappush(pq, (arr[i]/arr[lastIdx], i, lastIdx))
        count = 0
        while pq:
            count += 1
            cur = heapq.heappop(pq)
            if count == k:
                return [arr[cur[1]], arr[cur[2]]]
            if cur[2] > 1:
                heapq.heappush(pq, (arr[cur[1]]/arr[cur[2] - 1], cur[1], cur[2] - 1))
        return []

class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        mp = {}
        ans = []
        for i in range(len(arr)):
            for j in range(i + 1 , len(arr)):
                mp[arr[i] / arr[j]] = [arr[i] , arr[j]]
                ans.append(arr[i] / arr[j])
        ans.sort()

        return mp[ans[k - 1]]

#define pi pair<int, int>
class Compare {
public:
    bool operator()(pi p1, pi p2) { return (p1.first*p2.second > p1.second*p2.first); }
};

class Solution {
public:
    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
        priority_queue<pi, vector<pi>, Compare> pq;
        for(int i=0;i<arr.size()-1;++i)
            for(int j=i+1;j<arr.size();++j)
                pq.push({arr[i],arr[j]});
        while(--k) pq.pop();
        return vector<int> {pq.top().first, pq.top().second};
    }
};

class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        arr, n = sorted(arr), len(arr)
        pq = [(arr[0] / arr[-1], 0, n - 1)]
        seen = set([(0, n - 1)])

        while k > 1:
            _, i, j = heapq.heappop(pq)
            if i < n - 1 and (i + 1, j) not in seen:
                heapq.heappush(pq, (arr[i + 1] / arr[j], i + 1, j))
                seen.add((i + 1, j))
            if j > 0 and (i, j - 1) not in seen:
                heapq.heappush(pq, (arr[i] / arr[j - 1], i, j - 1))
                seen.add((i, j - 1))
            k -= 1

        _, i, j = pq[0]
        return [arr[i], arr[j]]

class Solution:
    def kthSmallestPrimeFraction(self, arr: List[int], k: int) -> List[int]:
        lst = []
        n = len(arr)
        for i in range(0, n):
            for j in range(i, n):
                tmp = - arr[i] / arr[j]
                if len(lst) < k:
                    heapq.heappush(lst, (tmp, [arr[i], arr[j]]))
                else:
                    if tmp > lst[0][0]:
                        heapq.heappushpop(lst, (tmp, [arr[i], arr[j]]))
        #         print(lst)
        # print(lst)
        return heapq.heappop(lst)[1]

class Solution:
    def mincostToHireWorkers(self, qualities: List[int], wages: List[int], k: int) -> float:
        def sort_by_wage_per_quality(quality_and_wage):
            quality, wage = quality_and_wage
            return wage / quality

        quality_and_wages = list(zip(qualities, wages))
        quality_and_wages.sort(key=sort_by_wage_per_quality)

        quality_heap = []
        quality_heap_sum = 0
        min_money = float('inf')

        for quality, wage in quality_and_wages:
            heapq.heappush(quality_heap, -quality)
            quality_heap_sum += quality

            if len(quality_heap) > k:
                quality_heap_sum += heapq.heappop(quality_heap)

            if len(quality_heap) == k:
                min_money = min(min_money, quality_heap_sum * wage / quality)

        return min_money

use std::cmp::*;
use std::collections::*;

struct Pair {
    wage: i32,
    quality: i32,
}

impl PartialEq for Pair {
    fn eq(&self, other: &Self) -> bool {
        (self.wage * other.quality).eq(&(other.wage * self.quality))
    }
}

impl Eq for Pair {}

impl PartialOrd<Pair> for Pair {
    fn partial_cmp(&self, other: &Pair) -> Option<Ordering> {
        Some((self.wage * other.quality).cmp(&(other.wage * self.quality)))
    }
}

impl Ord for Pair {
    fn cmp(&self, other: &Self) -> Ordering {
        (self.wage * other.quality).cmp(&(other.wage * self.quality))
    }
}

impl Solution {
    pub fn mincost_to_hire_workers(quality: Vec<i32>, wage: Vec<i32>, k: i32) -> f64 {
        let n = quality.len();
        let mut pairs = Vec::<Pair>::with_capacity(n);

        for (&wage, &quality) in wage.iter().zip(quality.iter()) {
            pairs.push(Pair {
                wage: wage,
                quality: quality
            });
        }

        pairs.sort_unstable();

        let mut max_heap = BinaryHeap::<i32>::new();
        let mut cost = f64::MAX;
        let uk = k as usize;
        let mut total_quality = 0f64;

        for i in 0..n {
            max_heap.push(pairs[i].quality);
            total_quality += pairs[i].quality as f64;

            if (max_heap.len() > uk) {
                if let Some(&quality) = max_heap.peek() {
                    total_quality -= quality as f64;
                }

                max_heap.pop();
            }

            if (max_heap.len() == uk) {
                let unit_cost = pairs[i].wage as f64 / pairs[i].quality as f64;
                cost = cost.min(total_quality * unit_cost);
            }
        }

        cost
    }
}

function mincostToHireWorkers(quality: number[], wage: number[], k: number): number {
    const workers: Record<string, number>[] = [];

    for (let i = 0; i < quality.length; i++) {
        workers.push({ percentage: wage[i] / quality[i], quality: quality[i] });
    }

    workers.sort((a, b) => a.percentage - b.percentage);

    let cost = Number.MAX_SAFE_INTEGER;
    let qualitySum = 0;
    let hired = new MaxPriorityQueue();


    for (let worker of workers) {
        qualitySum += worker.quality;
        hired.enqueue(worker.quality)

        if (hired.size() > k) {
            qualitySum -= hired.dequeue().element
        }

        if (hired.size() === k) {
            cost = Math.min(cost, qualitySum * worker.percentage)
        }
    }

    return cost;
};

class Solution:
    def mincostToHireWorkers(self, quality: List[int], wage: List[int], k: int) -> float:
        wpq = [(wage[i] / q, q) for i, q in enumerate(quality)]
        wpq.sort()
        ans, s, h = inf, 0, [inf]
        for p, q in wpq[:k-1]:
            s += q
            heappush(h, -q)

        for p, q in wpq[k-1:]:
            ans = min(ans, (s + q) * p)
            if q < -h[0]:
                s += heappop(h)
                s += q
                heappush(h, -q)

        return ans

class Solution {
    public double mincostToHireWorkers(int[] quality, int[] wage, int k) {
        int n = wage.length;
        double[][] workers = new double[n][2];
        for (int i = 0; i < n; i++) {
            workers[i][0] = (double) wage[i] / quality[i];
            workers[i][1] = quality[i];
        }
        Arrays.sort(workers, (a, b) -> {
            int comp = Double.compare(a[0], b[0]);
            return comp != 0 ? comp : Double.compare(a[1], b[1]);
        });

        double res = Double.MAX_VALUE;
        int sum = 0;
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());
        for (int i = 0; i < n; i++) {
            if (queue.size() == k) {
                sum -= queue.poll();
                queue.offer((int) workers[i][1]);
                sum += workers[i][1];
            }
            else {
                queue.offer((int) workers[i][1]);
                sum += workers[i][1];
            }
            if (queue.size() == k) {
                res = Math.min(res, sum * workers[i][0]);
            }
        }
        return res;
    }
}

public class Solution {
    public double MincostToHireWorkers(int[] quality, int[] wage, int k)
        {
            double ans = int.MaxValue;
            List<Tuple<int,int>> sorted = new List<Tuple<int, int>>();
            for (int i = 0; i < quality.Length; i++)
            {
                sorted.Add(new Tuple<int, int>(quality[i], i));
            }
            sorted = sorted.OrderBy( x => x.Item1).ToList();

            for (int i = 0; i < quality.Length; i++)
            {
                double capRatio = (double)wage[i] / (double)quality[i];
                double totalWage = wage[i];
                int count = 1;

                for (int j = 0; j < sorted.Count && count < k; j++)
                {
                    if (sorted[j].Item2 != i )
                    {
                        var offer = capRatio * sorted[j].Item1;
                        if (offer >= wage[sorted[j].Item2])
                        {
                            totalWage += offer;
                            count++;
                        }
                    }
                }
                if (count == k)
                {
                    ans = Math.Min(ans, totalWage);
                }
              
            }
            return ans;
        }       
}