4. Median of Two Sorted Arrays

There are two sorted arrays nums1 and nums2 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)).

You may assume nums1 and nums2 cannot be both empty.

Example 1:

nums1 = [1, 3]
nums2 = [2]

The median is 2.0

Example 2:

nums1 = [1, 2]
nums2 = [3, 4]

The median is (2 + 3)/2 = 2.5

解题要点：

题目要求时间复杂度为O(log (m+n))，由此我们可以采用归并排序。排好序后，找出中位数。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] a = new int[nums1.length + nums2.length];
        merge(a, nums1, nums2);        
        double res = 0;
        int mid = (a.length) / 2;
        if(a.length % 2 != 0) res = a[mid];
        else res = (a[mid] + a[mid - 1]) / 2.0;        
        return res;
    }
    public void merge(int[] result, int[] xs1, int[] xs2) {
        int i = 0, j = 0, k = 0;
        while(i < xs1.length && j < xs2.length) {
            if(xs1[i] < xs2[j]) result[k++] = xs1[i++];
            else result[k++] = xs2[j++];
        }
        while(i < xs1.length) result[k++] = xs1[i++];
        while(j < xs2.length) result[k++] = xs2[j++];
    }
}