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

第一个方法,维护一个大顶堆,其中有K个元素,遍历,算了没意思,不说了,贴代码

 1 class Solution {
 2 public:
 3     int kthSmallest(vector<vector<int>>& 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 };

第二个方法,二分查找,利用该矩阵每行每列增大的性质,可以通过从左下角开始走,遇到比mid值小或者等于mid的数,就加上所在列当前行包括当前行往上所有元素个数,然后往左移,否则就往上,直到遇到某个比mid值小或者等于mid的数。通过这种方式可以计算出小于等于mid值的元素个数。通过这个小函数,二分查找就可以了。贴代码

 1 class Solution {
 2 public:
 3     int kthSmallest(vector<vector<int>>& 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(vector<vector<int>>& 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 };

 

上一篇:cookie问题


下一篇:LeetCode 378. 有序矩阵中第K小的元素 Java