題目

給定兩個(gè)有序列表，大小分別為m和n。給出一個(gè)算法，以O(shè)（logn+logm）時(shí)間找出兩個(gè)列表合并后的有序列表中第k小元素

算法思想

設(shè)兩個(gè)數(shù)組為A[1...m],B[1...n]，則中間位置分別為m/2與n/2，假設(shè)A[m/2]>B[n/2]，那么A[m/2...m]在A+B的n/2+m/2之后，此時(shí)，若k<n/2+m/2，那么就可以排除A[m/2...m]的元素，在剩余元素再進(jìn)行上述操作，若k>n/2+m/2，那么就可以排除B[1...n/2]的元素，再剩余元素中尋找第k-n/2小項(xiàng)。

代碼：

#include <iostream>
#define MAXLEN 100
using namespace std;
int Search(int A[],int B[],int aLeft, int aRight, int bLeft, int bRight, int k)
{
    int aMiddle = (aLeft + aRight) / 2;
    int bMiddle = (bLeft + bRight) / 2;
    if (aLeft > aRight)
        return B[bLeft + k - 1];
    if (bLeft > bRight)
        return A[aLeft + k - 1];
    if (A[aMiddle] > B[bMiddle])
    {
        if (k <= (aMiddle - aLeft) + (bMiddle - bLeft) + 2)
            return Search(A, B, aLeft, aMiddle - 1, bLeft, bRight, k);
        else
            return Search(A, B,aLeft, aRight, bMiddle + 1, bRight, k - (bMiddle - bLeft) - 1);
    }
    else
    {
        if (k <= (aMiddle - aLeft) + (bMiddle - bLeft) + 2)
            return Search(A, B, aLeft, aRight, bLeft, bMiddle - 1, k);
        else
            return Search(A, B, aMiddle + 1, aRight, bLeft, bRight, k - (aMiddle - aLeft) - 1);
    }
}
int main(void)
{
    int alen, blen,k;
    int A[MAXLEN],B[MAXLEN];
    cin >> alen;
    for (int i = 0; i < alen; i++)
    {
        cin >> A[i];
    }
    cin >> blen;
    for (int i = 0; i < blen; i++)
    {
        cin >> B[i];
    }
    cin >> k;
    cout << "第" << k << "小元素是" << Search(A, B, 0, alen - 1, 0, blen - 1, k) << endl;
    system("pause");
    return 0;
}