in Algorithm

行列有序矩阵求第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也提到了这个问题,给了个简要的描述。

发表评论

  1. 有个很简单的解法可以做到O((m+n)log(max-min)),想想这个复杂度怎么来的就知道怎么做了。应该是最实用的方法了吧。