786. 第 K 個最小的素數分數

給你一個按遞增順序排序的數組 arr 和一個整數 k 。數組 arr 由 1 和若干 素數? 組成，且其中所有整數互不相同。

對于每對滿足 0 < i < j < arr.length 的 i 和 j ，可以得到分數 arr[i] / arr[j] 。

那么第?k?個最小的分數是多少呢?? 以長度為 2 的整數數組返回你的答案, 這里?answer[0] == arr[i]?且?answer[1] == arr[j] 。

示例 1：輸入：arr = [1,2,3,5], k = 3
輸出：[2,5]
解釋：已構造好的分數,排序后如下所示: 
1/5, 1/3, 2/5, 1/2, 3/5, 2/3
很明顯第三個最小的分數是 2/5示例 2：輸入：arr = [1,7], k = 1
輸出：[1,7]

提示：

• 2 <= arr.length <= 1000
• 1 <= arr[i] <= 3 * $10^4$
• arr[0] == 1
• arr[i] 是一個 素數 ，i > 0
• arr 中的所有數字 互不相同 ，且按 嚴格遞增 排序
• 1 <= k <= arr.length * (arr.length - 1) / 2

解題思路

題目需要求得第?k?個最小的分數，而分數定義為每對滿足 0 < i < j < arr.length 的 i 和 j ，得到的arr[i] / arr[j] ，因為數組arr是按遞增順序排序的，因此分數都是小于0的數字。為了避免浮點數的精度丟失，當我們比較當我們比較兩個分數?$\frac{a}{b}$和?$\frac{c}{d}$時，我們可以使用：$a\times d<b\times c$來替代 $\dfrac{a}{b} < \dfrac{c}{d} $的判斷，二者是等價的，這樣就可以避免計算機浮點數丟失造成的問題。因此我們在排序中需要根據上述規則進行自定義的排序，然后選出第k個最小的分數。

代碼

class Solution {
public:vector<int> kthSmallestPrimeFraction(vector<int> &arr, int k) {vector<pair<int, int>> cnt;for (int i = 0; i < arr.size(); ++i) {for (int j = i - 1; j >= 0; --j) {cnt.emplace_back(arr[j], arr[i]);}}sort(cnt.begin(), cnt.end(), [&](const auto &x, const auto &y) {return x.first * y.second < x.second * y.first;});return {cnt[k-1].first,cnt[k-1].second};}
};