Sponsored
Sponsored
This approach uses a min-heap to efficiently find the kth smallest fraction. By iterating through each pair of elements (i, j) in the array where i < j, we can calculate the fraction arr[i]/arr[j] and push it into the heap. The heap is then used to retrieve the k-th smallest element efficiently.
Time Complexity: O(n^2 log(n^2))
Space Complexity: O(n^2)
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public int[] KthSmallestPrimeFraction(int[] arr, int k) {
6 var pq = new PriorityQueue<(double, int, int), double>();
7 for (int i = 0; i < arr.Length; ++i)
8 for (int j = i + 1; j < arr.Length; ++j)
9 pq.Enqueue((arr[i] / (double)arr[j], i, j), arr[i] / (double)arr[j]);
10 while (--k > 0)
11 pq.Dequeue();
12 var result = pq.Dequeue();
13 return new int[] { arr[result.Item2], arr[result.Item3] };
14 }
15}In C#, we use the PriorityQueue class provided by .NET to help sort and retrieve elements based on the custom comparator of fraction values. The queue's enqueue and dequeue operations sort according to the smallest fraction value.
This approach uses binary search on the value of fractions. By implementing a search over the potential range of fraction values, the algorithm counts how many fractions are less than a given mid-point, narrowing down to the k-th one by manipulating the bounds of the potential fraction values. A two-pointer technique helps count the fractions efficiently.
Time Complexity: O(n log(max_fraction))
Space Complexity: O(1)
1using namespace std;
vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
double lo = 0.0, hi = 1.0, mid;
int n = arr.size();
vector<int> result(2);
while (hi - lo > 1e-9) {
mid = (lo + hi) / 2;
double maxFraction = 0;
int numerator = 0, denominator = 1;
int count = 0;
for (int i = 0, j = 1; j < n; ++j) {
while (i < j && arr[i] < arr[j] * mid)
i++;
count += i;
if (i > 0) {
double fraction = (double)arr[i - 1] / arr[j];
if (fraction > maxFraction) {
maxFraction = fraction;
numerator = arr[i - 1];
denominator = arr[j];
}
}
}
if (count < k)
lo = mid;
else {
hi = mid;
result[0] = numerator;
result[1] = denominator;
}
}
return result;
}In this C++ implementation, binary search is utilized with a two-pointer method to count and select fractions with values less than the midpoint. Adjusting the bounds based on the count helps find the k-th smallest fraction.