401. Kth Smallest Number in Sorted Matrix

//Binary search + sorted matrix search
class Solution { public: /** * @param matrix: a matrix of integers * @param k: An integer * @return: the kth smallest number in the matrix */ int findNumLess(vector<vector<int>> &matrix, int target){ const int m = matrix.size(); const int n = matrix[0].size(); int i = m - 1; int j = 0; int cnt = 0; while(i >= 0 && j < n){ if(matrix[i][j] <= target){ cnt += (i + 1); j++; } else{ i--; } } return cnt; } int kthSmallest(vector<vector<int>> &matrix, int k) { // write your code here const int m = matrix.size(); if(m == 0){ return 0; } const int n = matrix[0].size(); int start = matrix[0][0]; int end = matrix[m - 1][n - 1]; while(start + 1 < end){ int mid = start + (end - start) / 2; if(findNumLess(matrix, mid) >= k){ end = mid; } else{ start = mid; } } if(findNumLess(matrix, start) == k){ return start; } return end; } };


// PQ 类似BFS思想
两者的复杂度一样

Code(Language:C++) (Judger:cloudjudge-cluster-5)

struct cmp{
    bool operator()(const pair<int, int> &a, const pair<int, int> &b){
        return a.first > b.first; 
    }
}; 
class Solution {
public:
    /**
     * @param matrix: a matrix of integers
     * @param k: An integer
     * @return: the kth smallest number in the matrix
     */
    
    int kthSmallest(vector<vector<int>> &matrix, int k) {
        // write your code here
        const int m = matrix.size(); 
        if(m == 0){
            return 0; 
        }
        const int n = matrix[0].size(); 
        priority_queue<pair<int, int>, vector<pair<int, int>>, cmp> pq; 
        pq.push({matrix[0][0], 0}); 
        int cnt = 0; 
        vector<vector<int>> visited(m, vector<int>(n, 0));
        visited[0][0] = 1; 
        while(!pq.empty()){
            pair<int, int> p = pq.top(); 
            pq.pop(); 
            cnt++;
            if(cnt == k){
                return p.first; 
            }
            int x = p.second / n; 
            int y = p.second % n; 
            if(x + 1 < m && visited[x + 1][y] == 0){
                visited[x + 1][y] = 1; 
                pq.push({matrix[x + 1][y], (x + 1) * n + y}); 
            }
            if(y + 1 < n && visited[x][y + 1] == 0){
                visited[x][y + 1] = 1; 
                pq.push({matrix[x][y + 1], x * n + y + 1}); 
            }
            
        }
        return -1; 
    }
};