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))。

当然，这仍然不是最快的解法。查了下资料，发现这个问题确实蛮困难，有篇论文 研究了这个问题，对于一个(m\times n)的矩阵算法复杂度可以达到(O(n\log2m/n)) ，不过原始论文要砍25刀。

这篇Blog 也提到了这个问题，给了个简要的描述。