LWC 72: 786. K-th Smallest Prime Fraction
Problem:
A sorted list A contains 1, plus some number of primes. Then, for every p < q in the list, we consider the fraction p/q. What is the K-th smallest fraction considered? Return your answer as an array of ints, where answer[0] = p and answer1 = q.
Examples:
Input: A = [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, 2/3. The third fraction is 2/5. Input: A = [1, 7], K = 1 Output: [1, 7]
Note:
- A will have length between 2 and 2000.
- Each A[i] will be between 1 and 30000.
- K will be between 1 and A.length * (A.length 1) / 2.
思路1： 一种聪明的做法，如果A = [1, 7, 23, 29, 47]，那么有：
代码语言：javascript复制1/47 < 1/29 < 1/23 < 1/7
7/47 < 7/29 < 7/23
23/47 < 23/29
29/47可以采用优先队列的方法，把第一列先送入队列，因为他们一定是每行的最小，选出最小的之后，加入该行的后续元素。直到找到K-1个最小的元素。
代码如下：
代码语言：javascript复制 public int[] kthSmallestPrimeFraction(int[] a, int k) {
int n = a.length;
PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
int s1 = a[o1[0]] * a[o2[1]];
int s2 = a[o2[0]] * a[o1[1]];
return s1 - s2;
}
});
for (int i = 0; i < n-1; i ) {
pq.add(new int[]{i, n-1});
}
for (int i = 0; i < k-1; i ) {
int[] pop = pq.poll();
if (pop[1] - 1 > pop[0]) {
pop[1]--;
pq.offer(pop);
}
}
int[] peek = pq.peek();
return new int[]{a[peek[0]], a[peek[1]]};
}思路2： 二分，先找到这个第k小的数，接着再小范围暴力搜索，居然能过。
代码如下：
代码语言：javascript复制 public int[] kthSmallestPrimeFraction(int[] a, int K) {
double low = 0, high = 1;
double eps = 1e-8;
int n = a.length;
for(int rep = 0; rep < 50; rep){
double x = low (high-low) / 2;
int num = 0;
for(int i = 0;i < n;i ){
int ind = Arrays.binarySearch(a, (int)(x * a[i]));
if(ind < 0) ind = -ind - 2;
num = ind 1;
}
if(num >= K){
high = x;
}else{
low = x;
}
}
for (int i = 0; i < n; i) {
double find = a[i] * high;
int idx = Arrays.binarySearch(a, (int)find);
if (idx < 0) idx = -idx;
for (int j = -1; j <= 1; j) {
if (j idx >= 0 && j idx < n && Math.abs(a[j idx] - find) < eps) {
return new int[] {a[j idx], a[i]};
}
}
}
return new int[]{-1, -1};
}
