[LeetCode]K-th Smallest Prime Fraction

这道题我们把其转化成二维的话，我们把行看做分子，列看做分母，那么2D数组是从左向右递减，从上而下递增的，如下图所示：

那么这道题就可以转化为Kth smallest element in sorted matrix的题目。需要注意的是我们这里搜索范围是[0, 1]，而且是小数，我们搜索的mid不一定是在array里的。所以我们需要对二分做一些改良:

• 对于mid，我们仍然是统计小于等于mid的有多少个，这个可以再n + n = O(n)的时间内完成
• 同时我们需要记录小于等于mid在array当中存在的最大分数是什么，因为mid不一定在array中
• 假设小于等于mid的有d个
• 如果d < k，那么mid一定不是结果，lo = mid
• 如果d >= k那么mid有可能是结果，因为第k大的数可能有重复的，导致统计之后可能大于k。所以我们需要先存下来，之后继续更新可能的结果。

时间复杂度O(N * log W), W为搜索的宽度，这里为(hi - lo) / 1e-9，代码如下：

	class Solution {
	public:
	vector<int> kthSmallestPrimeFraction(vector<int>& A, int K) {
	int len = A.size();
	double lo = 0, hi = 1.0;
	vector<int> ret(2);
	while (hi - lo > 1e-9)
	{
	double mid = lo + (hi - lo) / 2.0;
	auto res = count(A, mid);
	if (res[0] < K)lo = mid;
	else
	{
	ret[0] = res[1];
	ret[1] = res[2];
	hi = mid;
	}
	}
	return ret;
	}
	private:
	vector<int> count(vector<int>& A, double target)
	{
	int len = A.size(), i = len - 1;
	vector<int> res(3, 0);
	for (int j = len - 1; j >= 0; --j)
	{
	while (i >= 0 && target * A[j] < A[i])
	--i;
	res[0] += i + 1;
	if (!res[2] || (i >= 0 && static_cast<long>(A[i]) * res[2] > static_cast<long>(res[1]) * A[j]))
	{
	res[1] = A[i];
	res[2] = A[j];
	}
	}
	return res;
	}
	};

view raw K-th Smallest Prime Fraction.cpp hosted with ❤ by GitHub