[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，代码如下：