Re: [閒聊] 每日leetcode已回收
※ 引述 《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
噓
05/10 12:34,
1年前
, 1F
05/10 12:34, 1F
推
05/10 13:00,
1年前
, 2F
05/10 13:00, 2F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 205 之 1553 篇)：