Kth Smallest Element in a Sorted Matrix

Question

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.

Solution

自己解的時候是用 PriorityQueue 解出來的。如果要優化的話，可以試著用 binary search 做。

這題讓我學到，binary search 有分兩種，一種是靠 index 來處理，另外一種是用 range。這題因為透過 index 所得到的元素是 unsorted，因此必須使用 range。九張教的 binary search template 基本上是建立在 index 的，因為他跳出 while loop 後，還得要 check nums[start] 跟 nums[end]，因此在這題不適用。

    public int kthSmallest(int[][] matrix, int k) {

        int start = matrix[0][0], end = matrix[matrix.length - 1][matrix[0].length - 1];
        while (start < end) {
            int mid = start + (end - start) / 2;
            int count = 0;
            int j = matrix[0].length - 1;
            for (int i = 0; i < matrix.length; i++) {
                while (j >= 0 && matrix[i][j] > mid) {
                    j--;
                }
                count += j + 1;
            }

            if (count < k) {
                start = mid + 1;
            } else {
                end = mid;
            } 
        }

        return end;
    }