# 2011-01-09  行列有序矩阵求第K个数

 **n\*n的行列有序的矩阵M，求第K大的数。行列有序是指每行、每列都是有序的。** 

~~最直接的办法就是给整个矩阵排序，然后找第K大的数。复杂度是(O(n^2logk))。其实还有更快的办法。~~ ~~假设行列都是增序。注意到在矩阵的对角线上中任选一点x，右下角的矩阵里面的数都大于或等于x，而这里包含了(x^2)个数。因此，必然可以找到一个位置x，使得 ((x+1)^2\leq n-k\leq x^2) 。 这样K就在 M(x+1, x+1) .. M(x+1, n) 和 M(x+1, x+1) .. M(n, x+1) 以及 x 这三个范围内。~~ ~~对这个范围内的数字排序，找第K个数字，复杂度是 (O(nlogk))~~

事实证明，我还是把这个问题想简单了，之前的解法是错的，因为取(a, a)点后，并不能保证a是除左上角矩阵最大的值，左下和右上仍然有可能有比(a, a)小的数字。

后来又想了个办法，做一个队列，伪代码如下：

```
findSortedMatrix {
    队列置空
    取M(0, 0)，入队
    for (int i=0; i < K; i++) {
        队列首元素出队，置为X 坐标为(x, y)
        取元素X的左边和下边的元素"插入"队列，使队列保持有序
    }
}
```

为了提高插入的速度，可以用堆的结构实现二分查找插入。这样，空间复杂度是(O(k)), 算法复杂度为(O(klogk))，最坏情况是空间(O(n^2)), 时间(O(klogn))。

当然，这仍然不是最快的解法。查了下资料，发现这个问题确实蛮困难，[有篇论文](http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal\&id=SMJCAT000013000001000014000001\&idtype=cvips\&gifs=yes) 研究了这个问题，对于一个(m\times n)的矩阵算法复杂度可以达到(O(n\log2m/n)) ，不过原始论文要砍25刀。

[这篇Blog](http://zhiqiang.org/blog/science/computer-science/median-algorithm-of-ordered-matrix.html) 也提到了这个问题，给了个简要的描述。


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://blog.log4think.com/k-th-number-in-sorted-matrix.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.