378.Kth Smallest Element in a Sorted Matrix¶

378.Kth Smallest Element in a Sorted Matrix¶

Tags: Binary Search Heap

Links: https://leetcode.com/problems/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^2$ .

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        priority_queue<int> pq;
        for (int i = 0; i < matrix.size(); ++i){
            for (auto e : matrix[i]){
                pq.push(e);
            }
        }
        int n = matrix.size();
        int rank = n * n - k + 1;

        while (--rank){
            pq.pop();
        }

        return pq.top();
    }
};

Runtime: 60 ms, faster than 42.41% of C++ online submissions for Kth Smallest Element in a Sorted Matrix.
Memory Usage: 13.5 MB, less than 22.73% of C++ online submissions for Kth Smallest Element in a Sorted Matrix.

priority_queue实现的是最大堆，所以寻要查找的是 $n^2 - k +1$ 的数值。时间复杂度 $O(n^2logK)$

经典的值域二分问题可以解的问题，首先数组的最小值是左上角的 $matrix[0][0]$ ，最大值是右下角的 $matrix[n−1][n−1]$ ，那么第 $k$ 小的数一定在这个区间内。

那么遍历整个数组，如果数组中的数小于等于target的元素小于K个，那么说明第K小的数比target大。如果数组中的数小于等于target的元素大于等于K个，就说明第K小的数小于等于target。题意：找一个最小的target，使得数组中小于等于target的数大于等于K。转化为找大于某个数中的最小值，其实就是lower_bound。

class Solution {
    int valueBinarySearch(vector<vector<int>>& matrix, int k, int target)
    {
        int count = 0;
        for (int i = 0; i < matrix.size(); ++i) {
            for (int j = 0; j < matrix[i].size(); ++j) {
                if (matrix[i][j] <= target) {
                    ++count;
                    continue;
                }
                break; //matrix[i][j]后面的数字肯定大于target
            }
        }
        return count;
    }
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int left = matrix[0][0], n = matrix.size(), right = matrix[n-1][n-1];

        while (left < right) {
            int mid = left + ((right - left) >> 1);
            int cnt = valueBinarySearch(matrix, k, mid);
            if (cnt >= k) right = mid;
            else left = mid + 1;
        }                   

        return left;
    }
};

Runtime: 40 ms, faster than 81.47% of C++ online submissions for Kth Smallest Element in a Sorted Matrix.
Memory Usage: 11.9 MB, less than 100.00% of C++ online submissions for Kth Smallest Element in a Sorted Matrix.

另一种利用列有序的方法：

class Solution {
public:
    int search(vector<vector<int>>& matrix, int target,int n)
    {
        //先从数组左下角元素开始,代表了从当前位置到右上角元素的矩形区域是还没有遍历的区间
        int row = n - 1 ,col = 0;
        int count = 0;
        while(row >=0 && col < n)
        {
            //如果这个当前数组元素小于目标值，说明这个元素以及同列的上方元素都小于目标值。
            //那么count加上row + 1,因为这一列已经遍历过了所以同时把col + 1，
            if(matrix[row][col] <= target)
            {
                count += row + 1;
                col ++;
            }else{//如果当前数组元素大于目标值，则这个元素以及同行的右方元素都大于目标值，
              //因为这一行已经遍历过了，所以col-1
                row --;
            }
        }
        return count;
    }
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        int left = matrix[0][0],right = matrix[n - 1][n - 1];
        //数组元素小于等于target的个数大于等于k的最小target，二分模板二
        //值域上的二分搜索
        while(left < right)
        {
            int mid = (left + right)/2;
            int count = search(matrix,mid,n);
            if(count >= k)
                right = mid;
            else
                left = mid + 1;
        }
        return left;
    }
};