求杨氏矩阵第k大的值

杨氏矩阵是这样的矩阵，它的每行每列都是由小到大排序的。以前板上post了一道google的算法题，大家在杨氏矩阵第k大问题上卡住了，前段时间无意发现一个解法，感觉很不错(非堆解法)。

解答是直接在杨氏矩阵中找第k个数没有什么有效的办法，但是可以“间接”寻找。
给定任意一个数，有办法判断该元素是矩阵中第几大的，
这样可以通过二分搜索找出一个数x, 这个数在给定杨氏矩阵中比k个数大。
找出这样的一个数后，就可以用杨氏矩阵搜索算法找出"刚好"小于x的数，这个数就是答案.

代码：
int GetOrder(int** pArr, int n, int m, int v);

int FindKth(int** pArr, int n, int m, int k)
{
        assert(pArr && m>0 && n>0 && k>0 && k<m*n);

        int nBeg = pArr[0][0];
        int nEnd = pArr[n-1][m-1];
        int nK = 0;
        int nMid = 0;
       
        int nPrev = -1;
        do
        {
                nMid = (nBeg + nEnd)/2;
                nK = GetOrder(pArr, m, n, nMid);
                if (nK == nPrev) break;
                nPrev = nK;

                if (nK < k)
                        nBeg = nMid;
                else
                        nEnd = nMid;
        }
        while(nK != k);

        int iCur = 0;
        int jCur = m-1;
        int nRet = 0;
        bool bFirst = true;
        while (iCur < n && jCur >= 0)
        {
                if (nMid > pArr[iCur][jCur])
                {
                        if (bFirst)
                        {
                                nRet = pArr[iCur][jCur];
                                bFirst = false;
                        }
                        else
                                nRet = nRet > pArr[iCur][jCur] ? nRet : pArr[iCur][jCur];

                        iCur++;
                }
                else
                {
                        jCur--;
                }
        }

        assert(!bFirst);

        return nRet;
}

int GetOrder(int** pArr, int m, int n, int v)
{
        assert(pArr && m>0 && n>0);

        int iCur = 0;
        int jCur = m-1;

        int nBiggerThan = 0;
        while (iCur < n && jCur >= 0)
        {
                if (pArr[iCur][jCur] >= v)
                {
                        nBiggerThan += n-iCur;
                        jCur--;
                }
                else iCur++;
        }

        return m*n - nBiggerThan;
}

wwwyhx 发表于 2011-6-11 12:00
解答是直接在杨氏矩阵中找第k个数没有什么有效的办法，但是可以“间接”寻找。
给定任意一个数，有办法判断 ...

如果矩阵里的都是整数，就没问题，因为二分可以遍历所有范围内的整数，但如果是浮点数，就不行了。。会有精度问题的。

wwwyhx 发表于 2011-6-11 12:00
代码：
int GetOrder(int** pArr, int n, int m, int v);

这种方法，有一个bug。
1 2 3 4
3 4 5 6
K=3该程序返回的是2（应该是3）
改一下，lessthan表示小于nMid的元素个数，lessthanorequalto表示小于等于nMide的元素个数。
当lessthan==k时，和该方法一样继续搜索。
当lessthan < k && lessthanorequalto >=k时，nMid就是第K个元素

堆的解法 时间复杂度是 O(klogk) 吧  

如果 不用堆的话 这个 代码 复杂度 是多少