786. K-th Smallest Prime Fraction

786. K-th Smallest Prime Fraction

 Complexity: O(n*log(k))

Solution 1:

 

class Solution {
public:
 struct fraction
{
  double val;
  int i,j;
  fraction(double d, int x, int y) : val(d), i(x), j(y){}
  bool operator< (const fraction& f)const{ return val > f.val;}
};

vector<int> kthSmallestPrimeFraction(vector<int>& A, int k)
{
  priority_queue<fraction>PQ;

  for(int i =0; i < A.size(); i++){
    PQ.push(fraction(static_cast<double> (A[i])/A.back(), i, A.size()-1 ));
  }
  while(k > 1){
    auto top = PQ.top();
    PQ.pop();
    top.j--;
    PQ.push(fraction(static_cast<double> (A[top.i])/A[top.j], top.i, top.j));
      k--;
  }

  return {A[PQ.top().i], A[PQ.top().j]};
}



};

Solution 2:

Compexity: N*C (c <= 31)

class Solution{
public:
  vector<int> kthSmallestPrimeFraction(vector<int>& A, int K)
  {
    const int n = A.size();
    double l = 0;
    double r = 1.0;
    while(l < r) {
      double m = (l + r)/2;
      double max_f = 0.0;
      int total = 0;
      int p, q = 0;
      for (int i = 0, j = 1; i < n - 1; ++i) {
       while (j < n && A[i] > m * A[j]) ++j;
        if(n == j)break;
        total += (n- j);
        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 {};
  }
};

Share: