给定两个数组 X 和 Y，它们都包含 n 个元素且都是有序的，如何找到它们的中位数？

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

template <typename T>
T find_median(T seq1[],T seq2[],int n,int low,int high)
{
    if(low>high)
        return (T)-999999;
    int k=(low+high)/2;
    if(k==n-1 && seq1[n-1]<=seq2[0])
        return seq1[n-1];
    else if(k<n-1 && seq1[k]>=seq2[n-k-1] && seq1[k]<=seq2[n-k])
        return seq1[k];
    else if(seq1[k]>seq2[n-k])
        return find_median(seq1,seq2,n,low,k-1);
    else
        return find_median(seq1,seq2,n,k+1,high);
}
 
template <typename T>
T two_array_median(T seq1[],T seq2[],int n)
{
    T median=find_median(seq1,seq2,n,0,n-1);
    if(median==(T)-999999)
        return find_median(seq2,seq1,n,0,n-1);
    else
        return median;
}

求两有序数组（长度不一定相等）合并后的第i个元素（不一定是中位数）。

思路分析：

假设两个有序数组是A[1...n]和B[1...n]，由于是寻找第i个元素，那么该元素只可能在A[1...i]与B[1...i]中，现在比较A[i/2]与B[i/2]
(1) A[i/2]==B[i/2]，那么A[i/2]（或者B[i/2])即要找的元素
(2) A[i/2]>B[i/2]，那么第i个元素在A[1...i/2]和B[i/2...i]中，递归的在上述两个数组中查找第i/2个元素
(3) A[i/2] 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

#include <iostream>
#include <string>
 
using namespace std;
 
template <typename T> 
T median2(T* X, T* Y, int size) 
{ 
    int m = (size - 1) / 2;
 
 
    if (X[m] == Y[m]) 
        return X[m]; 
    else if (X[m] > Y[m]) 
        return size == 1 ? Y[m] : median2 (X, Y + size - m - 1, m + 1); 
    else 
        return size == 1 ? X[m] : median2 (X + size - m - 1, Y, m + 1); 
}
 
int main(int argc,char* argv[])
{
 
    int t1[]={1,2,3,3,4,4,5,6,9};
    int t2[]={2,2,3,4,5,7,8};
    cout<<"median 3 :"<<median2(t1,t2,7);
 
    system("pause");
    return 0;
}


Related posts(相关文章):