leetcode378 Kth Smallest Element in a Sorted Matrix

思路1:

使用堆。

实现：

 1 class Solution 
 2 {
 3 public:
 4     int kthSmallest(vector<vector<int>>& matrix, int k) 
 5     {
 6         using pii = pair<int, int>;
 7         priority_queue<pii, vector<pii>, greater<pii>> q;
 8         int n = matrix.size();
 9         vector<int> v(n, 0);
10         for (int i = 0; i < n; i++) q.push(make_pair(matrix[i][v[i]], i));
11         pair<int, int> tmp;
12         for (int i = 0; i < k; i++)
13         {
14             tmp = q.top(); q.pop();
15             int id = tmp.second;
16             while (v[id] == n) 
17             {
18                 tmp = q.top();
19                 q.pop();
20                 id = tmp.second;
21             }
22             assert(v[id] != n);
23             v[id]++;
24             q.push(make_pair(matrix[id][v[id]], id));
25         }
26         return tmp.first;
27     }
28 };

思路2:

二分查找最小的x，满足大于x的元素数量不超过n * n - k个。

实现：

 1 class Solution 
 2 {
 3 public:
 4     bool check(vector<vector<int>>& matrix, int x, int g)
 5     {
 6         int n = matrix.size(), cnt = 0;
 7         for (int i = 0; i < n; i++)
 8         {
 9             int p = upper_bound(matrix[i].begin(), matrix[i].end(), x) - matrix[i].begin();
10             cnt += n - p;
11         }
12         return cnt <= g;
13     }
14     int kthSmallest(vector<vector<int>>& matrix, int k) 
15     {
16         int n = matrix.size();
17         if (n == 1) return matrix[0][0];
18         int l = matrix[0][0], r = matrix[n - 1][n - 1];
19         int ans = l;
20         while (l <= r)
21         {
22             int m = l + r >> 1;
23             if (check(matrix, m, n * n - k))
24             {
25                 ans = m;
26                 r = m - 1;
27             }
28             else l = m + 1;
29         }
30         return ans;
31     }
32 };

思路3:

由于矩阵每一行和每一列都是递增的，可以在思路2的基础上进行优化。

实现：

 1 class Solution 
 2 {
 3 public:
 4     bool check(vector<vector<int>>& matrix, int x, int g)
 5     {
 6         int n = matrix.size(), j = n - 1, cnt = 0;
 7         for (int i = 0; i < n; i++)
 8         {
 9             while (j >= 0 && matrix[i][j] > x) j--; //优化，不必每次都二分
10             cnt += n - 1 - j;
11         }
12         return cnt <= g;
13     }
14     int kthSmallest(vector<vector<int>>& matrix, int k) 
15     {
16         int n = matrix.size();
17         if (n == 1) return matrix[0][0];
18         int l = matrix[0][0], r = matrix[n - 1][n - 1];
19         int ans = l;
20         while (l <= r)
21         {
22             int m = l + r >> 1;
23             if (check(matrix, m, n * n - k))
24             {
25                 ans = m;
26                 r = m - 1;
27             }
28             else l = m + 1;
29         }
30         return ans;
31     }
32 };