786. K-th Smallest Prime Fraction
Đề Bài
You are given a sorted integer array arr containing 1 and prime numbers, where all the integers of arr are unique. You are also given an integer k.
For every i and j where 0 <= i < j < arr.length, we consider the fraction arr[i] / arr[j].
Return the kth smallest fraction considered. Return your answer as an array of integers of size 2, where answer[0] == arr[i] and answer[1] == arr[j].
Example 1:
Input: arr = [1,2,3,5], k = 3 Output: [2,5] Explanation: The fractions to be considered in sorted order are: 1/5, 1/3, 2/5, 1/2, 3/5, and 2/3. The third fraction is 2/5.
Example 2:
Input: arr = [1,7], k = 1 Output: [1,7]
Constraints:
2 <= arr.length <= 10001 <= arr[i] <= 3 * 104arr[0] == 1arr[i]is a prime number fori > 0.- All the numbers of
arrare unique and sorted in strictly increasing order. 1 <= k <= arr.length * (arr.length - 1) / 2
Follow up: Can you solve the problem with better than
O(n2) complexity?
Thuật Toán & Kỹ Thuật
⏱️ Thời gian
O(log n)
💾 Không gian
O(n)
Lời Giải
C++
0786-k-th-smallest-prime-fraction.cpp
class Solution {
public:
vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {
double left = 0.0, right = 1.0;
int n = arr.size();
while (left < right) {
double mid = (left + right) / 2;
int cnt = 0;
int a = 0, b = 0;
double max_fraction = 0.0;
for (int i = 0, j = 1; i < n; ++i) {
while (j < n && arr[i] > mid * arr[j]) {
j++;
}
cnt += n - j;
if (j < n && arr[i] * 1.0 / arr[j] > max_fraction) {
a = i;
b = j;
max_fraction = arr[i] * 1.0 / arr[j];
}
}
if (cnt == k) {
return {arr[a], arr[b]};
}
else if (cnt > k) {
right = mid;
}
else {
left = mid;
}
}
return {-1, -1};
}
};