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)
1#include <stdio.h>
2#include <stdlib.h>
3
4typedef struct {
5 double value;
6 int numerator;
7 int denominator;
8} Fraction;
9
10int cmp(const void* a, const void* b) {
11 Fraction* fa = (Fraction*)a;
12 Fraction* fb = (Fraction*)b;
13 return (fa->value > fb->value) - (fa->value < fb->value);
14}
15
16int* kthSmallestPrimeFraction(int* arr, int arrSize, int k, int* returnSize){
17 Fraction* fractions = (Fraction*)malloc(arrSize * arrSize * sizeof(Fraction));
18 int index = 0;
19 for (int i = 0; i < arrSize; ++i) {
20 for (int j = i + 1; j < arrSize; ++j) {
21 fractions[index].value = (double)arr[i] / arr[j];
22 fractions[index].numerator = arr[i];
23 fractions[index].denominator = arr[j];
24 ++index;
25 }
26 }
27 qsort(fractions, index, sizeof(Fraction), cmp);
28 int* result = (int*)malloc(2 * sizeof(int));
29 result[0] = fractions[k - 1].numerator;
30 result[1] = fractions[k - 1].denominator;
31 *returnSize = 2;
32 free(fractions);
33 return result;
34}In this C solution, a struct called 'Fraction' is defined to represent a fraction along with its value. The input array is iterated over pairs of indices to compute the fractions which are stored in an array. The array is then sorted based on the fraction values using the quicksort method. Finally, the k-th smallest fraction is returned.
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.