Re: [閒聊] 每日leetcode

看板Marginalman作者DJYOSHITAKA (franchouchouISBEST)時間1周前 (2024/05/10 23:11)推噓4(4推 0噓 4→)

留言8則, 5人參與討論串207/271 (看更多)

一開始自以為想說假設現在heap top是 arr[i]/arr[j] 那比它小一個的一定是 arr[i+1]/arr[j] or arr[i]/arr[j-1] 所以我就兩個都推進去下次pop出來就會是下一個最小的值，且可以handle k>n的case 所以我這樣寫 vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) { auto cmp = [&arr](pair<int,int> f1, pair<int,int> f2) { return (arr[f1.first]*arr[f2.second]) > (arr[f1.second]*arr[f2.first]); }; priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp); int n = arr.size(); //init pq.push({0, n-1}); for(int i=0; i<k-1; i++) { auto [nume_idx, deno_idx] = pq.top(); pq.pop(); if((nume_idx != deno_idx-1)) { pq.push({nume_idx+1, deno_idx}); pq.push({nume_idx, deno_idx-1}); } } return {arr[pq.top().first], arr[pq.top().second]}; } 結果這樣會找到重複pairㄚ操頭腦太簡單了乖乖看安殺== 確實能確保不推到重覆pair 要定分母or定分子ㄚ哀又想漬了 vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) { auto cmp = [&arr](pair<int,int> f1, pair<int,int> f2) { return (arr[f1.first]*arr[f2.second]) > (arr[f1.second]*arr[f2.first]); }; priority_queue<pair<int,int>, vector<pair<int,int>>, decltype(cmp)> pq(cmp); int n = arr.size(); //init for(int i=1; i<n; i++) pq.push({0, i}); for(int i=0; i<k-1; i++) { auto [nume_idx, deno_idx] = pq.top(); pq.pop(); if((nume_idx < deno_idx-1)) pq.push({nume_idx+1, deno_idx}); } return {arr[pq.top().first], arr[pq.top().second]}; } 其實就是把所有分數排成n-1排 arr[0]/arr[n-1] → arr[1]/arr[n-1] → arr[2]/arr[n-1] → … arr[0]/arr[n-2] → arr[1]/arr[n-2] → arr[2]/arr[n-2] → … … arr[0]/arr[1] 每一排我們都可以確保前面比後面小接下來就只要每個round確認哪一排的排頭最小，pop出來 pop K次就是答案了 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.146.144 (臺灣) ※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1715353897.A.4BB.html

推

sustainer123

05/10 23:12, 1周前 , 1^F

05/10 23:12, 1^F

推

SecondRun

05/10 23:20, 1周前 , 2^F

05/10 23:20, 2^F

→

SecondRun

05/10 23:21, 1周前 , 3^F

05/10 23:21, 3^F