378. Kth Smallest Element in a Sorted Matrix -M ！！！！！！！！！

Given an n x n matrix where each of the rows and columns is sorted in ascending order, return the kth smallest element in the matrix.

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

You must find a solution with a memory complexity better than O(n2).

 

Example 1:

Input: matrix = [[1,5,9],[10,11,13],[12,13,15]], k = 8
Output: 13
Explanation: The elements in the matrix are [1,5,9,10,11,12,13,13,15], and the 8th smallest number is 13

Example 2:

Input: matrix = [[-5]], k = 1
Output: -5

 

Constraints:

• n == matrix.length == matrix[i].length
• 1 <= n <= 300
• -109 <= matrix[i][j] <= 109
• All the rows and columns of matrix are guaranteed to be sorted in non-decreasing order.
• 1 <= k <= n2

 

Follow up:

• Could you solve the problem with a constant memory (i.e., O(1) memory complexity)?
• Could you solve the problem in O(n) time complexity? The solution may be too advanced for an interview but you may find reading this paper fun.

A:

1 : 全部放到一个vector, 然后sort，
2： PriorityQueue 
---------------------------Using max heap ------   但是没有利用到每行每列是排列好 的---------

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int m = matrix.size();        
        priority_queue<int, vector<int>> Q; // default is the max-heap
        for(auto & line:matrix)
        {
            for(auto v:line)
            {
                Q.push(v);
                if(Q.size()>k)
                {
                    Q.pop();
                }
            }
        }
        return Q.top();        
    }
};

3:  按照左上角，歇着 用这个方向  /    切，  每次消掉一定数目。直到不能再切了

class Solution {
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int m = matrix.size();
        int n = matrix[0].size();
        // cut like / , first chop top left, then along the diagonal
        int xl = 0, yl = 0, xr = 0, yr = 0;
        while(k>  xl - xr +1) // resutl not in current diagnal, need go next level
        {
            k -= xl - xr +1;
            if(xl < m-1)
                xl++;
            else
                yl++;
            if(yr < n-1)
                yr++;
            else
                xr++;
        }
        // result are in current /  
        vector<int> vec;
        while(xl >=0 and yl<n)   // forget to check boundary of xl, fuuuuuuuuck
        {
            vec.push_back(matrix[xl--][yl++]);
        }
        sort(vec.begin(), vec.end());
        return vec[k-1];
    }
};

-----------------------操，这个思路是不对的，为啥呢？  看这个例子：
[[1,3,5],[6,7,12],[11,14,14]]
3

-------------改正后呢，每次寻找当前一个斜切最小的。然后放进Min-heap里， 每次找到当前最小值以后，将其右边和下边的的位置放进min-heap------------

class Solution {       // beat only 6% of C++
public:
    int kthSmallest(vector<vector<int>>& matrix, int k) {
        int n = matrix.size();
        priority_queue<vector<int>, vector<vector<int>>, greater<>> minHeap;
        set<string> found; // use i;j to mark if a node has been added to heap
        minHeap.push(vector<int>{matrix[0][0],0,0});
        found.insert("0;0"); 
        int val, i,j;
        while(k>0){
            auto c = minHeap.top();
            --k;
            minHeap.pop();
            val = c[0],i = c[1],j=c[2];
            found.erase(to_string(i)+";"+to_string(j));         
            
            if(i+1 < n){//check right 
                string key = to_string(i+1)+";"+to_string(j);
                if(found.find(key) == found.end()){
                    found.insert(key);
                    minHeap.push(vector<int>{matrix[i+1][j],i+1,j});
                }
            }
            if(j+1 < n){//check down
                string key = to_string(i)+";"+to_string(j+1);
                if(found.find(key) == found.end()){
                    found.insert(key);
                    minHeap.push(vector<int>{matrix[i][j+1],i,j+1});
                }
            }            
        }
        return val;
    }
};

        priority_queue<vector<int>, vector<vector<int>>, greater<>> minHeap;

Better solution : binary search according to matrix values. here.

------Mistakes:

1:  又一次不会写priority_queue.   这次错在， <  >    写成了 (  )