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)
1
public class Solution {
public int[] KthSmallestPrimeFraction(int[] arr, int k) {
double lo = 0.0, hi = 1.0;
while (hi - lo > 1e-9) {
double mid = (lo + hi) / 2.0;
int count = 0;
int p = 0, q = 1;
double maxFraction = 0.0;
int i = 0;
for (int j = 1; j < arr.Length; 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;
p = arr[i - 1];
q = arr[j];
}
}
}
if (count < k) lo = mid;
else {
hi = mid;
result[0] = p;
result[1] = q;
}
}
return result;
}
}The C# implementation uses binary search and a two-pointer method to count and track fractions. Adjusting the fraction value bounds is key to finding the k-th smallest fraction.