4、Median of Two Sorted Arrays

此题难度高，但是因为面试曾被问到，所以记录一下

Example

nums1 = [1 , 3]
nums2 = [2]
The median is 2.0
nums1 = [1 , 2]
nums2 = [3 , 4]
The median is (2 + 3)/2 = 2.5

解法
要寻找第k小的元素，那么总是保持数组A的当前元素（即A[a]）为当前最小元素（如果不是，则交换A和B数组，使这一条成立），然后弹出该元素（即++a），然后再递归调用寻找第k-1小的元素。

这需要注意的地方在于：

A.length + B.length 为偶数的时候，中位数有两个，要取平均
A.length + B.length 为奇数的时候，中位数只有一个

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length = nums1.length + nums2.length;
        if (length%2 == 1){
            return recrusive(nums1, nums2, 0, nums1.length-1, 0, nums2.length-1, length/2 + 1);
        } else {
            return (recrusive(nums1, nums2, 0, nums1.length-1, 0, nums2.length-1, length/2)+recrusive(nums1, nums2, 0, nums1.length-1, 0, nums2.length-1, length/2 + 1))/2.0;
        }
    }


    public double recrusive(int[] A, int[] B, int i, int i2, int j, int j2, int k){
        int m = i2-i+1;
        int n = j2-j+1;
        if (m > n) return recrusive(B, A, j, j2, i, i2, k);
        if (m == 0) {
            return B[j+k-1];
        }
        if (k == 1){
            return Math.min(A[i], B[j]);
        }
        int posA = Math.min(k/2, m);
        int posB = k-posA;
        if(A[i+posA-1] == B[j+posB-1]){
            return A[i+posA-1];
        }else if (A[i+posA-1] < B[j+posB-1]){
            return recrusive(A, B, i+posA, i2, j, j+posB-1, k-posA);
        }else {
            return recrusive(A, B, i, i+posA-1, j+posB, j2, k-posB);
        }
    }
}