leetcode

Solution to some Leetcode problems written in C++

git clone git://git.dimitrijedobrota.com/leetcode.git

0378.cpp (1773B)

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