[LeetCode]Kth Smallest Element in a Sorted Matrix

这道题和Find K Pairs with Smallest Sum是一样的，Matrix都是自上而下从左到右sort的，区别就是这道题直接把Matrix给我们了，而那道题是隐形的条件。我们可以用和那道题一样的解法，就是把m * n的array看为m个长度为n的sorted list，然后找到第k个。但是这道题我们有常数空间的解法，假设min和max分别为array的最大值和最小值，因为我们知道答案一定在min和max之间，所以我们可以用值域上的二分。也就是每次我们选定mid值，统计所有小于等于mid的数的数量count，如果count < k说明答案在右半边，lo = mid + 1; 如果count >= k，说明答案在左半边，hi = mid。用v代表max和min的差值，时间复杂度T(v) = T(v / 2) + m + n，考虑m + n一般小于v, 时间复杂度O(v * log v), 代码如下：