• 欢迎光临~

# 4. Median of Two Sorted Arrays

Given two sorted arrays `nums1` and `nums2` of size `m` and `n` respectively, return the median of the two sorted arrays.

The overall run time complexity should be `O(log (m+n))`.

Example 1:

```Input: nums1 = [1,3], nums2 = [2]
Output: 2.00000
Explanation: merged array = [1,2,3] and median is 2.
```

Example 2:

```Input: nums1 = [1,2], nums2 = [3,4]
Output: 2.50000
Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
```

`public static double findMedian(int[] A, int[] B) {    int lenA = A.length;    int lenB = B.length;    int totalLen = lenA + lenB;    if (totalLen % 2 == 1)        return helper(A, 0, lenA, B, 0, lenB, totalLen / 2 + 1);    else {        int var1 = helper(A, 0, lenA, B, 0, lenB, totalLen / 2);        int var2 = helper(A, 0, lenA, B, 0, lenB, totalLen / 2 + 1);        return (double)(var1 + var2) / 2;    }}private static int helper(int[] A, int beginA, int lenA, int[] B, int beginB, int lenB, int k) {    if (lenA > lenB)        return helper(B, beginB, lenB, A, beginA, lenA, k);    if (lenA == 0)        return B[beginB + k - 1];    if (k == 1)        return Math.min(A[beginA], B[beginB]);    int ma = Math.min(lenA, k / 2);//把k分成两部分    int mb = k - ma;    if (A[beginA + ma - 1] < B[beginB + mb - 1])        return helper(A, beginA + ma, lenA - ma, B, beginB, lenB, k - ma);//把A数组前面ma个元素去掉    else if (A[beginA + ma - 1] > B[beginB + mb - 1])        return helper(A, beginA, lenA, B, beginB + mb, lenB - mb, k - mb);//把B数组前面mb个元素去掉    else        return A[beginA + ma - 1];}`