问题 - 求矩阵中第K大的数是多少？ - 51Nod

问题 - 求矩阵中第K大的数是多少？ - 51Nod

2个整数数组A,B，长度分别为m，n。从A，B中各选1个元素A[i],B[j]，相加后得到C[i,j]，共有m*n种选择方式，对应m*n个数，求这m*n个数中第K大的数是多少？

1、碰到这个问题的一般思路是，把m*n个数先求出来，然后用Nth-Elemnet，找出第k大的数。Nth-Element就是快排变形的那个partition，线性时间，这里不延伸讲了。这样的话时间复杂度O(m*n)，空间复杂度O(m*n)。

2、对于第一种方法，时间复杂度还好说，空间复杂度实在问题比较大，是否可以不求出这m*n个元素就直接找打第K大的数呢？

可以这样，先对A，B分别排序。复杂度n*log(n) + m*log(m)，排序后我们就发现第k大的数一定在Min = A[0] + B[0] <= C[k] <= A[n] + B[m] = Max，而且从Min到Max，K是递减，如果用二分法找这个C[k]，然后在A和B中判断，有多少个数比C[k]大。如果恰好有k-1个数比C[k]大，则C[k]是第K大的数。考虑有相等的情况，如果比C[K]大的数不到K个，而比C[K]小的数不到m*n - k个，则说明等于C[K]的数有多个（当然直接判断=也可以），那么C[K]就是第k大的数。

总结一下这个思路，就是在Min和Max之间，二分找这个和，然后在排序好的数组A,B中，统计有多少个数大于这个和。

在这个思路的基础上，如何统计有多少个数的和大于给定的数C[k]呢？我们可以枚举数组A中的元素，然后利用二分，在数组B中找到C[k] - A[i]对应的元素B[j]，那么所有比B[j]大的元素同A[i]的和，都大于C[k]。这样就可以写出一个n*log(m)*log(Max - Min) + n*log(n) + m*log(m)的程序来解决这个问题，空间复杂度O(1)

3、对于方法2，有一个简单的优化，就是如果n > m，也就是数组B的长度大于数组A的长度，如果枚举数组B，效率会更高，空间还是O(1)，时间变为了min(m,n)*log(max(n,m))*log(max - min) + n*log(n) + m*log(m)

4、对于方法2和3，都还可以进一步优化，优化的关键点在于：枚举数组A，在数组B中二分找一个数。如果改用头尾指针的方式，平摊下来是线性的。方法如下：

先用一个指针指向数组A的头，一个指向数组B的尾，如果A[0] + B[m] < C[k]，A的指针后移，判断A[1] + B[m]，如果A[0] + B[m] > C[k]，则B的指针前移，判断A[0] + B[m-1]。简单说就是< C[k]，A的指针后移，> C[k]，B的指针前移。不过问题的关键在于计数，同时统计大于C[k]的小于C[k]的数有多少个。如果A[0] + B[m] < C[k]，则A[0] + B[0],B[1]......B[m-1]都小于<C[k]，小于的计数+m,如果A[0] + B[m] > C[k]，则A[1],A[2]......A[n]+B[m]都大于C[k]，大于计数+n，这样，就可以写出一个(m+n)*log(Max-Min)+ n*log(n) + m*log(m)的程序，来解决这个问题。

到此为止，优化到头了么？其实此问题可以转为在杨氏矩阵中找第k大的值，问题还有优化的空间，关键在于Log(Max - Min)，可以优化到Log(m*n)，后者适用范围就不仅仅是整数了，实数范围都可以，但具体方法比较复杂，有兴趣大家可以再深入研究一下。

        static private int[] A, B;

        //求第K个元素

        static long KthElement(long k)

        {

            //该数肯定位于upper和lower之间

            long upper = (long)A[A.Length - 1] * B[B.Length - 1], lower = A[0] * B[0];

            return Solve(upper, lower, k);

        }

        //二分查找该值

        static long Solve(long upper, long lower, long count)

        {

            if (upper == lower) return upper;

            long mid = (upper + lower) >> 1;

            if (Counter(mid) >= count)

                return Solve(upper, mid + 1, count);

            if (Counter(mid - 1) < count)

                return Solve(mid - 1, lower, count);

            return mid;

        }

        //统计比指定value大的数有多少个

        static long Counter(long value)

        {

            int i = 0, j = B.Length - 1;

            long count = 0;

            while (i < A.Length && j >= 0)

            {

                if ((long)A[i] * (long)B[j] > value)

                {

                    count += A.Length - i;

                    j--;

                }

                else

                    i++;

            }

            return count;

        }

    }

http://blog.csdn.net/huangxy10/article/details/8084652
https://segmentfault.com/q/1010000000715010
http://zhiqiang.org/blog/science/computer-science/median-algorithm-of-ordered-matrix.html

给定 n×n$n\times n$ 的实数矩阵，每行和每列都是递增的，求这 n2$n^2$ 个数的中位数。

使用类似Tarjan的线性中位数的方法，每次找每列中位数，然后找中位数的中位数，之后可以删除前一半列的上半部分或者后一半列的下半部分，这样可以实现复杂性 O(nlog2n)$O(n{\log }^{2}n)$ 。

但是这个问题是有 O(n)$O(n)$ 的算法的，在Top Language Google Group的Obtuse Sword的指点下，找到了这个问题的原始论文：Generalized Selection and Ranking: Sorted Matrices。事实上这篇论文证明了更强的结论：

对于一个 n×m$n\times m$ ( n≤m$n\le m$ )的矩阵，若每行和每列都是递增的，则可以在 O(nlog2m/n)$O(n\log 2m/n)$ 找到第 k$k$大的数。

算法的基本思路是将矩阵依次对半划分成更小的子矩阵，然后删除不可能包含所求中位数的子矩阵。通过对每次划分后子矩阵个数的估计，发现此算法时间复杂度为 O(nlog2m/n)$O(n\log 2m/n)$ 。

使用同样的技巧，可以证明更更强的结论(这个算法具体过程就没细看了):

一堆 ni×mi$n_i\times m_i$ ( ni≤mi$n_i\le m_i$ )的矩阵，若每个矩阵的每行和每列都是递增的，则selection problem（即找第 k$k$ 大的数）的时间复杂度为 O(∑nilog2mi/ni)$O(\sum n_i\log 2m_i/n_i)$ 。

Read full article from 问题 - 求矩阵中第K大的数是多少？ - 51Nod