LeetCode 378. Kth Smallest Element in a Sorted Matrix

Posted on Edited on In 
1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        final int R = matrix.length, C = matrix[0].length;
        int[] sorted = new int[R * C];
        int idx = 0;
        for (int[] row : matrix)
            for (int num : row)
                sorted[idx++] = num;
        Arrays.sort(sorted);
        return sorted[k - 1];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        final int R = matrix.length;
        PriorityQueue<int[]> q = new PriorityQueue<>((a, b) -> a[0] - b[0]);
        for (int i = 0; i < R; ++i)
            q.offer(new int[]{matrix[i][0], i, 0});
        for (int i = 0; i < k - 1; ++i) {
            int[] now = q.poll();
            if (now[2] != R - 1)
                q.offer(new int[]{matrix[now[1]][now[2] + 1], now[1], now[2] + 1});
        }
        return q.poll()[0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        int n = matrix.length;
        int left = matrix[0][0], right = matrix[n - 1][n - 1];
        while (left < right) {
            int mid = left + ((right - left) >> 1);
            if (check(matrix, k, mid, n))
                right = mid;
            else
                left = mid + 1;
        }
        return left;
    }
    private boolean check(int[][] matrix, int k, int mid, int n) {
        int i = n - 1, j = 0, cnt = 0;
        while (i >= 0 && j < n) {
            if (matrix[i][j] <= mid) {
                cnt += i + 1;
                ++j;
            } else {
                --i;
            }
        }
        return cnt >= k;
    }
}