给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。

请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n))。

示例 1:

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

中位数是 2.0

示例 2:

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

中位数是 (2 + 3)/2 = 2.5

public double FindMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.Length;
    int n = nums2.Length;
    int i = 0;
    int j = 0;
    int index = 0;
    int[] datas = new int[m+n];

    //合并排序
    while(i<m && j<n)
    {
        if(nums1[i] < nums2[j])
        {
            datas[index++] = nums1[i++];
        }
        else
        {
            datas[index++] = nums2[j++];
        }
    }

    //填充剩下的
    while(j<n)
    {
        datas[index++] = nums2[j++];
    }

    while(i<m)
    {
        datas[index++] = nums1[i++];
    }

    int mid = (m+n)/2;
    int offset = (m+n)%2;
    if(offset == 0)
    {
        return (datas[mid]+datas[mid-1])/2.0f;
    }else
    {
        return datas[mid];
    }
}

使用合并排序的方式，将两个数组合并排序到一个数组中，然后判断长度为偶数就取中间两个的平均数，为奇数就去取中间那位。时间复杂度应该是O(n)或O(m)，空间复杂度是O(m+n)。还有更优的解法。