Solution 1

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

。題目假設

兩個陣列是排序過的

。重要問題

。直覺

用 merge sort 可以很簡單的解決

。解決方法可行性

merge sort 先排序兩個陣列，之後找中間值即可，可以做到

。解決方案

merge sort時，是用兩個指針分別指向Ａ和Ｂ，然後開始比對，將小的先放入結果陣列，再放入大的，放入後指針向前

如果一樣，則兩個都放入，然後兩個指針都向前，做到某一個指針已經到陣列結尾，然後把還沒走完的陣列append到結果

然後再判斷奇偶數，取中位數即可

。資料結構

array

。複雜度

O(m+n)

public double findMedianSortedArrays(int[] A, int[] B) {
    int m = A.length;
    int n = B.length;

    boolean isEven = (m+n) % 2 == 0 ? true : false;
    int aPointer = 0;
    int bPointer = 0;
    long[] mergedArray = new long[m+n];

    int index = 0;
    while (aPointer < m && bPointer < n) {
        if (A[aPointer] < B[bPointer]) {
            mergedArray[index++] = A[aPointer];
            aPointer++;
        } else if (A[aPointer] > B[bPointer]) {
            mergedArray[index++] = B[bPointer];
            bPointer++;
        } else if (A[aPointer] == B[bPointer]) {
            mergedArray[index++] = A[aPointer];
            mergedArray[index++] = B[bPointer];
            aPointer++;
            bPointer++;
        }
    }

    if (aPointer < m)
        for (int i=aPointer; i<m; i++)
            mergedArray[index++] = A[i];
    if (bPointer < n)
        for (int i=bPointer; i<n; i++)
            mergedArray[index++] = B[i];

    int mid = (m+n)/2;
    if (isEven) {
        return (double) (mergedArray[mid]+mergedArray[mid-1])/2;
    }

    return (double) mergedArray[mid];
}