本文主要是介绍786. K-th Smallest Prime Fraction,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
花花酱
class Solution {
public:vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {const int n = A.size();double l = 0, r = 1.0;while(l < r){double m = (l + r)/2;double max_f = 0.0;int total = 0;int p, q = 0;int j = 1;for(int i = 0; i < n - 1; i++){while(j <n && A[i] > m*A[j]) ++j;total +=(n -j);if(n == j) break;const double f = static_cast<double>(A[i])/A[j];if(f > max_f){p = i;q = j;max_f = f;}}if(total == K){return {A[p], A[q]};}else if(total > K) r = m;else l = m;}return {};}
};
这篇关于786. K-th Smallest Prime Fraction的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!