> For the complete documentation index, see [llms.txt](https://hao-fu-1.gitbook.io/oj/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://hao-fu-1.gitbook.io/oj/binarysearch/er-fen-range/kth-smallest-element-in-a-sorted-matrix.md).

# 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).