第28天(简单题中等题 二分查找)

打卡第二十八天
1道简单题+2道中等题

题目:

思路:双指针+二分查找

代码:

class Solution {
public:vector<int> kthSmallestPrimeFraction(vector<int>& arr, int k) {const int n = (int)arr.size();// 初始化二分查找的左右边界，分数值范围在0到1之间double l = 0, r = 1.0;// 开始二分查找while (l != r) {double mid = (l+r)/2; // 计算中间值int cnt = 0, i = 0, x = 0, y = 1;// 对每个分母arr[j]，统计分子arr[i]使得arr[i]/arr[j] < midfor (int j = 1; j < n; ++j) {// 移动指针i，找到满足arr[i]/arr[j] < mid的最大iwhile ((double)arr[i]/arr[j] < mid) {// 更新当前找到的最大分数（最接近mid的分数）if (arr[i] * y > arr[j] * x) {x = arr[i];y = arr[j];}++i;}cnt += i; // 累计所有满足条件的分数个数}if (cnt == k) {return {x,y}; // 找到正好第k小的分数} else if (cnt < k) {l = mid; // 需要更大的阈值} else {r = mid; // 需要更小的阈值}}return {};}
};

耗时≈一小时 明天继续