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

	class Solution {
	public:
	int kthSmallest(vector<vector<int>>& matrix, int k) {
	int m = matrix.size(), n = m? matrix[0].size(): 0;
	if(!m || !n)return -1;
	int lo = matrix[0][0], hi = matrix[m - 1][n - 1];
	while(lo < hi)
	{
	int mid = lo + (hi - lo) / 2;
	int c = count(matrix, mid);
	if(c >= k)hi = mid;
	else lo = mid + 1;
	}
	return lo;
	}
	private:
	int count(vector<vector<int>>& matrix, int k)
	{
	int m = matrix.size(), n = m? matrix[0].size(): 0;
	int i = m - 1, j = 0, res = 0;
	while(i >= 0 && j < n)
	{
	while(i >= 0 && matrix[i][j] > k)--i;
	res += i + 1;
	++j;
	}
	return res;
	}
	};

view raw Kth Smallest Element in a Sorted Matrix.cpp hosted with ❤ by GitHub