LeetCode 378. Kth Smallest Element in a Sorted Matrix

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

Note:
You may assume k is always valid, 1 ≤ k ≤ n².

解析：矩阵中每一行是有序的，每一列也是有序的，但问题是前一行的最后一个元素未必小于后一行的第一个元素，所以这个会增加了难点。C++ stl中提供了一个方法nth_element，这个前面的题目中有使用，返回第N个位置上的元素，N之前的元素都比它小，N之后的元素都比它大，但是不保证前面和后面元素都是有序的。直接看代码。

解法1：

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        vector<int> one_vec;
        int row_size = matrix.size();
        int col_size = matrix[0].size();
        for(int i=0; i < row_size; i++)
            for(int j = 0; j < col_size; j++)
            {
                one_vec.push_back(matrix[i][j]);
            }
        nth_element(one_vec.begin(), one_vec.begin() + k-1, one_vec.end());
        return one_vec[k-1];
    }
};

这种解法其实并没有完全利用数组有序的特征，下面看二分查找的方式。因为矩阵每一行是有序的，所以最小的元素在matrix[0][0]，最大的元素在matrix[n-1][n-1]位置。然后计算出mid=(left+right)/2，遍历每一行，然后统计比mid小的元素数量cnt，这里采用upper_bound方法。如果cnt<k，则让left=mid+1，否则right=mid。这样最终left=right，此时返回的即是第K个元素。代码如下：

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int left = matrix[0][0];
        int right = matrix.back().back();
        while(left < right)
        {
            int mid = (left + right) / 2;
            int cnt = 0;
            for(int i =0; i< n; i++)
            {
                auto it = upper_bound(matrix[i].begin(), matrix[i].end(), mid);
                cnt += it - matrix[i].begin();
            }
            if(cnt < k)
                left = mid + 1;
            else 
                right = mid;
        }
        return left;
    }
};

这个方法比较巧的地方在于对二分查找的改造，看一下时间执行情况：

参考：

https://www.cnblogs.com/grandyang/p/5727892.html