Re: [閒聊] 每日leetcode

[oinishere (是oin捏)]

※ 引述 《Rushia (早瀬ユウカの体操服)》 之銘言：
: 　
: https://leetcode.com/problems/k-th-smallest-prime-fraction/description
: 786. K-th Smallest Prime Fraction
: 給你一個遞增的質數不重複數字陣列，第一個數字是1，求出不重複質數可組成的第k
: 小分數。
: 　
: 思路：
: 1.求第k小的數字，會先想到heap，最小分數一定是分子為1的，所以我們把除了arr[0]以
:   外的分母都配1丟進heap。
: 　
: 2.從heap pop k次，每次都讓分子變大並重新入隊，因為陣列排序好了所以一直讓索引變
:   大就好。
: 　



全部丟進去

sort

第k個

回傳

我覺得 我做法超爛

來看解答好了

姆咪



class Solution {
public:



    vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k)
    {

        int len = arr.size();

        vector<pair<int,int>> save;

        for(int i = 0 ; i < len ; i ++)
        {
            for( int j = i+1; j < len ; j ++)
            {
                save.push_back({arr[i],arr[j]});
            }
        }

        sort(save.begin(),save.end(),[](const auto &a , const auto &b){
            return a.first/(double)a.second < b.first/(double)b.second;
        });

        return {save[k-1].first , save[k-1].second};

    }
};

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.133.52 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715315611.A.248.html
噓 JIWP: 對你超爛
推 pandix: 大師