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)
1import java.util.PriorityQueue;
2
3public class KthSmallestPrimeFraction {
4 public int[] kthSmallestPrimeFraction(int[] arr, int k) {
5 int n = arr.length;
6 PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> arr[a[0]] * arr[b[1]] - arr[b[0]] * arr[a[1]]);
7 for (int i = 0; i < n - 1; i++) {
8 pq.offer(new int[]{i, n - 1});
9 }
10 int[] result = new int[2];
11 while (k-- > 0) {
12 result = pq.poll();
13 if (result[1] - 1 > result[0]) {
14 pq.offer(new int[]{result[0], result[1] - 1});
15 }
16 }
17 return new int[]{arr[result[0]], arr[result[1]]};
18 }
19}In Java, we use a priority queue to store potential fractions using the comparator to sort by fraction value. We repeatedly extract the smallest fraction and use the k-th extraction to obtain our result.
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.