lintcode 2つのソート配列の中位数

2つのソート配列AとBはそれぞれmとn個の数を含み、2つのソート配列の中位数を見つけ、時間複雑度はO(log(m+n))であることが要求される.配列A=[1,2,3,4,5,6]B=[2,3,4,5]を与え,中位数3.5は配列A=[1,2,3]B=[4,5]を与え,中位数3題リンク:http://www.lintcode.com/zh-cn/problem/median-of-two-sorted-arrays/# この問題の難易度の等級は困難で、難しければ要求時間の複雑度がO(logn)で、それでは普通の遍歴を使って従来することができなくて、そのような時間の複雑度はO(n)です.まずランダムな位置でAを2つの部分に分けます:left_A | right_A A[0],A[1],...,A[i-1]|A[i],A[i+1],...,A[m-1]Aにはm個の元素があるので、m+1種のカット(i=0〜m)がある.そのうち:left_A.size() = i,right_A.size() = m-i.注意:i=0の場合、left_Aが空で、i=mの場合、right_Aは空です.同様に、ランダムな位置でBを2つの部分に切ります:left_B | right_B[0]、B[1],...,B[j-1]|B[j],B[j+1],...,B[n-1]はleft_Aとleft_Bは集合を入れ、right_Aとright_Bは別の集合を入れる.left_と名前を付けますpartとright_part: left_part | right_part A[0]、A[1],...,A[i-1]|A[i],A[i+1],...,A[m-1]B[0],B[1],...,B[j-1]|B[j],B[j+1],...,B[n-1]確保できれば:1)left_part.size() == right_part.size()2)max(left_part)<=min(right_part)では、{A,B}のすべての要素を2つの長さが等しい部分に分割し、1つの部分は常に別の部分より大きい.次に、中央値=(max(left_part)+min(right_part)/2.この2つの条件を確認するには、次のようにします.
(1)i+j==m-i+n-j(または:m-i+n-j+1)n>=mの場合、i=0〜m、j=(m+n+1)/2-i(2)B[j-1]<=A[i]、A[i-1]<=B[j]を設定する必要があります.なぜn>=mを必要としますか.0<=i<=mおよびj=(m+n+1)/2−iのため、jが正当なインデックスであることを確認する必要がある.nの場合
[0,m]でiを検索し、B[j−1]<=A[i]およびA[i−1]<=B[j]となるように、分割点i(j=(m+n+1)/2−i)を見つけた.<1>imin=0、imax=mを設定し、[i min、imax]<2>i=(imin+imax)/2、j=(m+n+1)/2-i<3>現在left_part.size() == right_part.size().また,(1)B[j−1]<=A[i]とA[i−1]<=B[j]の3つの場合のみ,分割点iが見つかったことを意味し,探索を停止する.(2)B[j−1]>A[i]はA[i]が小さすぎることを意味する.iを調整してB[j−1]<=A[i]を得る必要がある.一方、iが減少するとjが増加するため、B[j−1]が増加し、A[i]が減少するため、iは減少するしかない.だからiを増やさなければなりません.すなわち,探索範囲を[i+1,imax]に調整する.したがって、imin=i+1となり、次に<2>ステップに戻る.(3)A[i−1]>B[j]はA[i−1]が大きすぎることを意味し,iを減らしてA[i−1]<=B[j]を得る必要がある.したがって、imax=i-1を設定して<2>ステップに戻ります.切り分け点iが見つかった場合、中央値はmax(A[i-1],B[j-1])または(max(A[i-1],B[j-1])+min(A[i],B[j])/2(m+nが偶数の場合)である
ここで,辺値i=0,i=m,j=0,j=n,すなわちA[i−1],B[j−1],A[i],B[j]が存在しない場合を考える.max(left_part)<=min(right_part)を確保するためです.したがって,iとjが辺値(A[i−1],B[j−1]ともに存在しない場合,B[j−1]<=A[i],A[i−1]<=B[j]を検証しなければならない.ただし、A[i−1],B[j−1],A[i],B[j]のいくつかが存在しない場合は、この2つの条件のうちの1つをチェックする必要はない.例えば、i=0の場合、A[i-1]が存在しない場合、A[i-1]<=B[j]をチェックする必要はない.したがって、[0,m]でiを検索し、(j==0またはi==mまたはB[j−1]<=A[i])および(i==0またはj==nまたはA[i−1]<=B[j])j=(m+n+1)/2−iが検索サイクル中に、(1)(j==0またはi==mまたはB[j−1]<=A[i])および(i==0またはj=nまたはA[i−1]<=B[j]<=B[j])の3つのケースしかないように、分割点iを見つける必要がある.条件を満たして検索を停止します.(2)j>0とi A[i]iが小さすぎてiが増加する.(3)i>0とjB[j]iが大きすぎてiが減少する.多くのことを言っていますが、次はコードです.

class Solution {
public:
    /**
     * @param A: An integer array.
     * @param B: An integer array.
     * @return: a double whose format is *.5 or *.0
     */
    double findMedianSortedArrays(vector A, vector B) {
        //int minidx = 0, maxidx = m, i, j, num1, mid = (m + n + 1) >> 1,num2;
        if (A.size() > B.size()) return findMedianSortedArrays(B,A);
        int m = A.size(),n = B.size();
        int imin = 0,imax = m,half_len = (m + n + 1) / 2,i,j,max_of_left,min_of_right;
        while (imin <= imax) {
            i = (imin + imax) / 2;
            j = half_len - i;
            if (i < m && j > 0 && B[j - 1] > A[i]) imin = i + 1;
            else if (i > 0 && j < n && B[j] < A[i - 1]) imax = i - 1;
            else {
                if (i == 0) max_of_left = B[j - 1];
                else if (j == 0) max_of_left = A[i - 1];
                else max_of_left = max(A[i - 1],B[j - 1]);
                break;
            }
        }
        if ((m + n) % 2 == 1) return max_of_left;
        if (i == m) min_of_right = B[j];
        else if (j == n) min_of_right = A[i];
        else min_of_right = min(A[i],B[j]);
        return (max_of_left + min_of_right) / 2.0;
    }
};