（算法）两个有序数组的第k大的数

题目：

有两个数组A和B，假设A和B已经有序（从大到小），求A和B数组中所有数的第K大。

思路：

1、如果k为2的次幂，且A,B 的大小都大于k，那么

考虑A的前k/2个数和B的前k/2个数，

如果A[k/2]<B[k/2]，说明A的前k/2个数一定在A和B总的前k个数中，因此只需要在A的k/2之后的数和B中查找第k/2大的数；

否则，说明A的前k/2个数一定在A和B总的前k个数中，因此只需要在B的k/2之后的数和A中查找第k/2大的数；

递归实现即可；

2、如果A+B的数组大小大于k

二分法，考虑A的前一半m/2和B的前一半n/2，

假设A[mid]<B[mid]：

如果m/2+n/2大于k，则表明第k大存在于A和B的前一半中；否则，只需在A的m/2之后的数和B中找第k-m/2大的数；

假设A[mid]>B[mid]：

如果m/2+n/2大于k，则表明k存在于A和B的前一半中；否则，只需在B的n/2之后的数和A中找第k-n/2大的数；

递归实现即可；

代码：

#include<iostream>

using namespace std;

// if length of A && length of B >=k

// k is power of 2

int FindKthElem_1(int A[],int aLeft,int aRight,int B[],int bLeft,int bRight,int k){

    /*

    if(aLeft>aRight)

        return B[bLeft+k-1];

    if(bLeft>bRight)

        return A[aLeft+k-1];

    */

    if(k==){

        if(A[aLeft]>B[bLeft])

            return B[bLeft];

        else

            return A[aLeft];

    }

    int aKth=aLeft+(k>>)-;

    int bKth=bLeft+(k>>)-;

    if(A[aKth]<B[bKth])

        return FindKthElem_1(A,aKth+,aRight,B,bLeft,bRight,(k>>));

    else

        return FindKthElem_1(A,aLeft,aRight,B,bKth+,bRight,(k>>));

}

// if length of A + length of B >=k

int FindKthElem_2(int A[],int aLeft,int aRight,int B[],int bLeft,int bRight,int k){

    if(aLeft>aRight)

        return B[bLeft+k-];

    if(bLeft>bRight)

        return A[aLeft+k-];

    int aMid=aLeft+((aRight-aLeft)>>);

    int bMid=bLeft+((bRight-bLeft)>>);

    int halfLen=aMid-aLeft+bMid-bLeft+;

    if(A[aMid]<B[bMid]){

        if(halfLen>k){

            return FindKthElem_2(A,aLeft,aRight,B,bLeft,bMid-,k);

        }

        else{

            return FindKthElem_2(A,aMid+,aRight,B,bLeft,bRight,k-(aMid-aLeft+));

        }

    }

    else{

        if(halfLen>k){

            return FindKthElem_2(A,aLeft,aMid-,B,bLeft,bRight,k);

        }

        else{

            return FindKthElem_2(A,aLeft,aRight,B,bMid+,bRight,k-(bMid-bLeft+));

        }

    }

}

int main(){

    int A[]={,,,,,};

    int B[]={,,,,,};

    int aLen=sizeof(A)/sizeof(A[]);

    int bLen=sizeof(B)/sizeof(B[]);

    int k;

    while(true){

        cout<<"Please Input k:"<<endl;

        cin>>k;

        cout<< FindKthElem_1(A,,aLen-,B,,bLen-,k) <<endl;

        cout<< FindKthElem_2(A,,aLen-,B,,bLen-,k) <<endl;

    }

    return ;

}

巴特西

（算法）两个有序数组的第k大的数

题目：

思路：

代码：

最新文章

热门文章