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 <vector>
2#include <queue>
3#include <utility>
4
5using namespace std;
6
7vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
8 int n = arr.size();
9 auto cmp = [&](pair<int, int>& a, pair<int, int>& b) {
10 return arr[a.first] * arr[b.second] > arr[b.first] * arr[a.second];
11 };
12 priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(cmp)> pq(cmp);
13 for (int i = 0; i < n; ++i) pq.emplace(i, n - 1);
14 pair<int, int> result;
15 while (k--) {
16 result = pq.top();
17 pq.pop();
18 if (result.second - 1 > result.first) {
19 pq.emplace(result.first, result.second - 1);
20 }
21 }
22 return {arr[result.first], arr[result.second]};
23}This C++ code uses a priority queue (min-heap) to maintain the smallest fractions. The priority queue orders elements based on the current fraction value represented by elements in the array. We then extract the smallest element k times to find and return the k-th smallest fraction.
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
Utilizing JavaScript, binary search reduces the possible range for fraction values. A two-pointer setup helps count smaller fractions, determining bounds for pinpointing the k-th smallest fraction.