LeetCode/solutions/378. Kth Smallest Element in a Sorted Matrix.md

378. Kth Smallest Element in a Sorted Matrix

思路

这道题让我们求各行各列分别有序的矩阵中第K小的元素。难点在于矩阵只是局部（各行或各列）有序，整体可能是无序的。

由于是有序的，所以很容易想到可以用二分查找解此题。由于一般的二分都是对数组的下标二分，所以很容易陷入这个定势思维中去。

这里我们需要对元素二分而不是元素的下标二分: 我们很容易知道整个矩阵的最大值high和最小值low分别是右下角和左上角元素，所以最终的结果就是在区间[low, high]内。 设mid = (low+high)/2，那么该如何更新low和high呢？我们可以计算有多少个（设为count）数小于等于mid，那么

• 若count < k，说明不到k个数小于等于mid，即最终结果肯定大于mid，所以更新low = mid + 1；
• 否则，说明至少k个数小于等于mid，即最终结果肯定不大于mid，所以更新high = mid（注意这里没有减一）。

所以问题的关键就在于如何计算有多少个数小于等于mid，分为两个思路。

思路一

我们一行一行（或者一列一列）地遍历矩阵，计算每一行有多少个数小于mid，最后累加起来就可以了。 对于每一行，因为是有序的，所以我们可以用二分查找的思路计算有多少个数小于mid，可直接使用STL中的upper_bound函数：

• upper_bound(first, last, val)返回有序数组或容器的[first, last)范围内第一个大于val的元素的位置(指针或者迭代器);

而lower_bound(first, last, val)返回有序数组或容器的[first, last)范围内第一个大于或等于val的元素的位置;

总的时间复杂度即O(nlogn * logM)，其中M等于最大值与最小值的差值。

思路二

思路一只利用了行有序（或只利用了列有序），所以还有优化的空间。

我们从左下角出发（或者从右上角出发，类似），

• 若当前值（设下标为i,j）小于等于mid，因为当前值正上方的值更小些，所以累加上这些值的个数count += (i+1)，然后往右移（j++）进入下一循环；
• 否则，即当前值大于mid，那我们只需上移（i--）即可。

由于我们只会右移或者上移，所以移动步数为2n，即线性复杂度。所以总的时间复杂度为O(n * logM)，其中M等于最大值与最小值的差值。

C++

思路一

class Solution {
private:
    // 记录有多少数小于等于target
    int Count_No_Greater(const vector<vector<int>>& matrix, int target){
        int n = matrix.size(), count = 0;
        for(int i = 0; i < n; i++)
            count += upper_bound(matrix[i].begin(), 
                                 matrix[i].end(), target) - matrix[i].begin();
        return count;
    }
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int low = matrix[0][0], high = matrix.back().back();
        
        while(low < high){
            int mid = (high - low) / 2 + low;
            // count记录有多少数小于等于mid
            int count = Count_No_Greater(matrix, mid);
            if(count < k) low = mid + 1; // 不到k个数小于等于mid
            else high = mid; // 至少k个数小于等于mid
        }
        return low;
    }
};

思路二

仅Count_No_Greater函数与思路一不同

// 记录有多少数小于等于target
int Count_No_Greater(const vector<vector<int>>& matrix, int target){
    int n = matrix.size(), count = 0;
    int i = n - 1, j = 0;
    while(i >= 0 && j < n){
        if(matrix[i][j] > target) i--;
        else{
            count += (i + 1);
            j++;
        }
    }
    return count;
}