LeetCode Median of Two Sorted Arrays

LeetCode 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)).

題意：求兩個有序數組的組成一個新的數組的中位數

思路：題目轉換為求第k大的數，如果總個數是奇數的話，就是求第中間的數了，如果是偶數的話，就是找到兩個中間的，求平均數。

求第k大的數：首先假設我們求的是兩個數組A和B中第k個數，為了我們每次都能折半查找，我們比較A[k/2]和B[k/2]這兩個數，如果A[k/2-1]

class Solution {
public:
    double findMedianSortedArrays(int A[], int m, int B[], int n) {
        int size = m + n;
        int k = (m + n + 1) / 2;
        if (size & 1)
            return findKth(A, m, B, n, k);
        else return (findKth(A, m, B, n, k) + findKth(A, m, B, n, k+1)) / 2;
    }
    
    double findKth(int A[], int m, int B[], int n, int k) {
        if (m > n)
            return findKth(B, n, A, m, k);
        if (m == 0)
            return B[k - 1];
        if (k == 1)
            return A[0] < B[0] ? A[0] : B[0];
        
        int index = k / 2;  
        int left = index < m ? index : m;  
        int right = k - left;  
          
        if (A[left - 1] < B[right - 1])     
           return findKth(A + left, m - left, B, n, right);  
        else if (A[left - 1] > B[right - 1])  
           return findKth(A, m, B + right, n - right, left);  
        else return A[left - 1];  
    }
};