leetcode

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 };