leetCode-002 Median of Two Sorted Arrays

There are two sorted arrays A and B of size m and n respectively. Find the median of the two sorted arrays. The overall run time

complexity should be O(log (m+n)).

有兩個有序的數組，找出這兩數組整合後的中位數，要求時間複雜度O(nlogn)

    要找這兩個排序數組的中位數，數組長度分别是Len(A)=m和Len(B)=n

    如果m+n是奇數，則中位數是兩個排序數組組合之後的第(m+n+1)/2個數

    如果m+n是偶數，則中位數是兩個排序數組組合之後的第(m+n)/2和第(m+n)/2+1個數的平均值

    則原題的目标可以轉化為兩個數組整合之後的第K小數問題

    解決方案1，

        由于A和B都是排好序的數組，借用歸并的思想，把兩個數組進行合并，然後取kth，複雜度是O(n+m)。 不符合題設要求。

    解決方案2

        O(log(m+n)) 表明必須使用二分法來解決。

        以一次疊代為例，保證m<n的順序，要找兩個集合第k小數，我們分别看A[pa-1]和B[pb-1], 其中pa = k/2, pb = k-k/2。如果A[pa-1]<B[pb-1]，則A[pa-1]及其之前的所有元素都應該包含在前k小集合裡，第k小的點肯定在 A[pa~m-1]或B[0~pb]中；是以下一步疊代就變成了求數組A[pa~m-1]和B[0~pb]中的第k-pa小值問題。