0378.cpp (1773B)
1 class Solution { 2 public: 3 int kthSmallest(vector<vector<int>> &matrix, int k) { 4 const int n = matrix.size(); 5 priority_queue<int> heap; 6 for (int i = 0; i < n; i++) { 7 for (int j = 0; j < n; j++) { 8 heap.push(matrix[i][j]); 9 if (heap.size() > k) heap.pop(); 10 } 11 } 12 return heap.top(); 13 } 14 }; 15 16 class Solution { 17 typedef tuple<int, uint8_t, uint8_t> tp; 18 19 public: 20 int kthSmallest(vector<vector<int>> &matrix, int k) { 21 const int n = matrix.size(); 22 priority_queue<tp, vector<tp>, greater<tp>> heap; 23 for (int i = 0; i < min(n, k); i++) 24 heap.push({matrix[i][0], i, 0}); 25 26 for (int i = 1; i < k; i++) { 27 const auto [elem, row, col] = heap.top(); 28 heap.pop(); 29 if (col + 1 < n) heap.push({matrix[row][col + 1], row, col + 1}); 30 } 31 return get<0>(heap.top()); 32 } 33 }; 34 35 class Solution { 36 int count(const vector<vector<int>> &matrix, int mid) { 37 const int n = matrix.size(); 38 int i = n - 1, j = 0, count = 0; 39 while (i >= 0 && j < n) { 40 if (matrix[i][j] > mid) 41 i--; 42 else { 43 count += i + 1; 44 j++; 45 } 46 } 47 return count; 48 } 49 50 public: 51 int kthSmallest(vector<vector<int>> &matrix, int k) { 52 const int n = matrix.size(); 53 int low = matrix.front().front(), high = matrix.back().back(); 54 while (low <= high) { 55 const int mid = low + (high - low) / 2; 56 const int ans = count(matrix, mid); 57 if (ans < k) 58 low = mid + 1; 59 else 60 high = mid - 1; 61 } 62 return low; 63 } 64 };