378. Kth Smallest Element in a Sorted Matrix

发表于 | 分类于

Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.

Note that it is the kth smallest element in the sorted order, not the kth distinct element.

Example:

1
2
3
4
5
6
7
8
matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,
return 13.

Note:
You may assume k is always valid, 1 ? k ? n2.

解法1：Heap

用heap的思想，先把第一排或者第一列放入queue中，然后操作k-1次，每一次拿出一个元素，并且把他下面一行的元素也推入queue中。最后在堆顶的就是所求的答案。
C++

1

Java

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
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
public class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        if (matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        PriorityQueue<Tuple> queue = new PriorityQueue<>(new Comparator<Tuple>() {
            public int compare(Tuple left, Tuple right) {
                return left.val - right.val;
            }
        });
        int row = matrix.length;
        int col = matrix[0].length;
        for (int j = 0; j < col; j++) {
            queue.offer(new Tuple(0, j, matrix[0][j]));
        }
        for (int count = 0; count < k - 1 ; count++) {
            Tuple temp = queue.poll();
            if (temp.x == row - 1) continue;
            queue.offer(new Tuple(temp.x + 1, temp.y, matrix[temp.x + 1][temp.y]));
        }
        return queue.poll().val;
    }
    class Tuple {
        int x;
        int y;
        int val;
        public Tuple(int x, int y, int val) {
            this.x = x;
            this.y = y;
            this.val = val;
        }
    };
}

解法2：Range version of Binary Search, Time Complexity O(NlogM)

先确定最小值和最大值，知道了范围以后。找出中间点，然后统计有多少数小于他的值，如果总数小于k那么知道k个数一定在右半边。以此类推
O(NlogM): N是行数，M是search range = max - min

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
27
28
29
public class Solution {
    public int kthSmallest(int[][] matrix, int k) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int n = matrix.length;
        int low = matrix[0][0];
        int high = matrix[n - 1][n - 1] + 1;   // [low, high)
        while (low < high) {
            int mid = low + (high - low ) / 2;
            int count = 0, j = matrix[0].length - 1; // seach from the end of the column
            for (int i = 0; i < matrix.length; i++) {
                while (j >= 0 && matrix[i][j] > mid) j--;
                count += (j + 1);   // calcualte in this row, how many elements are smaller than mid
            }
            if (count < k) {
                low = mid + 1;
            } else {
                high = mid;
            }
        }
        return low;
    }
}