leetcode 378 有序矩阵的第K小元素

 1 class Solution {
 2 public:
 3     int kthSmallest(vectorint>>& matrix, int k) 
 4     {
 5         priority_queue<int,vector<int>,less<int>> queJudge;
 6         int m = matrix.size();
 7         int n = matrix[0].size();
 8         for(int i = 0 ; i < m ; i++)
 9         {
10             for(int j = 0 ; j < n ; j++)
11             {
12                 if(queJudge.size()<k)
13                 queJudge.push(matrix[i][j]); 
14                 else 
15                 {
16                     if(matrix[i][j]<=queJudge.top())
17                     {
18                         queJudge.pop();
19                         queJudge.push(matrix[i][j]);
20                     }
21                 }   
22             }
23         }
24         return queJudge.top();
25     }
26 };

 1 class Solution {
 2 public:
 3     int kthSmallest(vectorint>>& matrix, int k) 
 4     {
 5         int n = matrix.size();
 6         int left = matrix[0][0];
 7         int right = matrix[n-1][n-1];
 8         while(left<right)
 9         {
10             int mid = left + (right-left)/2;
11             if(cherk(matrix,k,mid,n))
12             right = mid;
13             else
14             left = mid+1;
15         }
16         return left;
17     }
18     bool cherk(vectorint>>& matrix,int k,int mid,int n)
19     {
20         int i = n-1;
21         int j = 0;
22         int num = 0;
23         while(i>=0 && j<n)
24         {
25             if(matrix[i][j]<=mid)
26             {
27                 num += i+1;
28                 j++;
29             }
30             else
31             i--;
32         }
33         return num>=k;
34     }
35 };