一开始自以为
想说 假设现在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次就是答案了