Kth Smallest Element in a Sorted Matrix

https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/description/

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.

Thoughts

这道题走了很多弯路。首先矩阵是只保证每行每列内部是升序的，并不是说整个是升序的。因此下一行第一个不一定比上一行的非首元素大。而且不能像拨香蕉一样每次把最外面那行和列扔掉，因为它们中元素可能会比包着的矩阵中的元素大。

看到找最小首先容易想到的方法是用堆来做，找k次最小即可。

在这里我们用另一种二分的思路。刚开始看到这题有二分的tag我把自己局限到传统的从index角度做，可能是受到search_a_2d_matrix影响吧。后来看提醒才知道它是在矩阵所有可能取值的范围做二分，即matrix[0][0]到matrix[n-1][n-1]的所有可能值。每次取中值，判断整个矩阵中有多少个小于等于中值的元素。如果数量比中值小了，说明中指取得太小，把start前移至mid + 1;反之则把end移到mid. 直到最后start == end，此时刚好数量==k。返回start即可。

思维陷阱在于看到排好的序，想当然以为是根据index做二分，又想有没有O(nlgn)的解法，从而卡住。 如果完全没给排好序的条件，倒是更容易想到。 这次分界点是矩阵中第k小的数，range前段是对于里头任何一个元素，在矩阵中的比它小的数目小于k; range后段是里头任何一个元素，在矩阵中比它小的数目大于k。

在找矩阵中有多少个元素小于中指时，可以根据矩阵排好序的特性继续用二分。由于这个二分不是想说的重点，就略去了。

Code

class Solution {
    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;
            for (int i = 0; i < matrix.length; i++) {
                for (int j = 0; j < matrix[i].length; j++) {
                    count = matrix[i][j] <= mid ? count + 1 : count;
                }
            }
            if (count < k) {
                start = mid + 1;
            } else {
                end = mid;
            }
        }

        return start;
    }

}

Analysis

时间复杂度是O(lg(MAX-MIN)n^2), 可以用二分法继续优化中间找数目那块得O(lg(MAX-MIN)nlgn).