378. 有序矩阵中第K小的元素

1.题目描述

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。

请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

示例：

提示：

你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。

2.方法1（二分查找）

矩阵的左上角为最小值，右下角为最大值，以最小值最大值为上下边界，求出中间值mid，遍历矩阵，统计到中间值mid有多少个数count，如果count小于k，说明第k小的数在mid后面，low = mid + 1，否则high = mid - 1。

3.代码

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int m = matrix.size(), n = matrix[0].size();
        int low = matrix[0][0];
        int high = matrix[m-1][n-1];

        while(low <= high){
            int mid = low + (high - low) / 2;
            int count = 0;

            for(int i = 0;i < m;++i){
                for(int j = 0;j < n && matrix[i][j] <= mid;++j){//统计到中间大的数据中有几个数
                    count++;
                }
            }
            if(count < k){//如果count < k，说明第k小的数在mid后面
                low = mid + 1;
            }
            else{
                high = mid - 1;
            }
        }
        return low;
    }
};
           

4.复杂度分析

时间复杂度：O(nlog(r−l))，二分查找进行次数为 O(log(r−l))，每次操作时间复杂度为 O(n)。

空间复杂度：O(1)。