Google : 就地寻找两数组中第k大的数

两个数组，就地(不用额外空间)找出合并后第k大的数

int[] a= [3 1 7]
int[] b = [4 9]
k: 3
return 4.

连个临时变量都不让声明吗。。。还是能用O(1)的空间。

如果可以使用O(k)空间的话，priority_queue就行了。如果O(1)空间，感觉就要sort两个array，然后binary search了

如果可以使用O(k)空间的话，priority_queue就行了。如果O(1)空间，感觉就要sort两个array，然后binary search了
MontagueHu 发表于 2011-6-20 09:02

    说说我想到的一个解法：
    O(1)的空间，就是说不能再分配一个数组把所有数装进来

    可以写一个函数，它负责取“假设”两个数组合并后的第i个元素的地址，然后就和一个数组的Topk问题一样求解

int* GetIndex(int nIndex, int a[], int n, int b[], int m)
{
        assert(nIndex>=0 && a && b && n>0 && m>0);

        if (nIndex < n)
                return a+nIndex;

        return b+nIndex-n;
}

int _inner_get_kth(int a[], int n, int b[], int m, int k, int nStart, int nEnd)
{
        assert(a && b && n>0 && m>0 && k>=0 && k<m+n);

        int i = nStart;
        int j = nEnd;
        bool bInLeft = true;
        while (i != j)
        {
                if (*GetIndex(i, a, n, b, m) <= *GetIndex(j, a, n, b, m))
                {
                        if (bInLeft)
                                j--;
                        else
                                i++;
                }
                else
                {
                        int* pi = GetIndex(i, a, n, b, m);
                        int* pj = GetIndex(j, a, n, b, m);
                        int nTmp = *pi;
                        *pi = *pj;
                        *pj = nTmp;

                        bInLeft = !bInLeft;
                }
        }

        if (i+1 == k) return *GetIndex(nStart, a, n, b, m);

        if (i+1 > k)
                return _inner_get_kth(a, n, b, m, k, nStart, i-1);

        return _inner_get_kth(a, n, b, m, k, i+1, nEnd);
}

int GetKth(int a[], int n, int b[], int m, int k)
{
        assert(a && b && n>0 && m>0 && k>=0 && k<m+n);
        return _inner_get_kth(a, n, b, m, k, 0, m+n-1);
}

O(n)时间复杂度

不就是快排的partition的过程修改一下吗。又或者用线性时间的寻找中位数的方法。

逻辑上连在一起好了……物理上连不连其实不重要啊

我的想法
1）两个数组各自快排
2）两个索引分别从大到小遍历，计数topk=0，当索引指向的当前值大的，topk++，该索引--，知道topk=k。

反正都在内存里面，Partition稍微变化一下
另外可以考虑一下，不能全部load进内存的一串整数的Kth问题

我勒个去，我手滑不小心点到“杂草“，怎么办= =求W大，K姐帮忙后台改一下= =