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 也提到了这个问题,给了个简要的描述。