Median of Two Sorted Arrays leetcode

第一种方法 先把两个数组合并, 然后返回新数组的中间值 时间复杂度 O(m + n) 空间 O(m + n)

public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] tem = new int[m + n];
        int idx1 = m - 1;
        int idx2 = n - 1;
        int idx = idx1 + idx2 + 1;
        while (idx1 >= 0 && idx2 >= 0) {
            if (nums1[idx1] >= nums2[idx2]) {
                tem[idx--] = nums1[idx1--];
            } else {
                tem[idx--] =  nums2[idx2--];
            }
        }
        if (idx2 < 0) {
            for (int i = idx1; i >= 0; i--) {
                tem[idx--] = nums1[i];
            }
        }
        if (idx1 < 0) {
            for (int i = idx2; i>= 0; i--) {
                tem[idx--] = nums2[i];
            }
        }
        if ((m + n) % 2 == 1) {
            return tem[(m + n) / 2 ];
        } else {
            return (tem[(m + n) / 2] + tem[(m + n) / 2 - 1]) / 2.0;
        }
    }
}

可以依照：寻找一个unioned sorted array中的第k大（从1开始数）的数。因而等价于寻找并判断两个sorted array中第k/2（从1开始数）大的数。

特殊化到求median，那么对于奇数来说，就是求第(m+n)/2+1（从1开始数）大的数。

而对于偶数来说，就是求第(m+n)/2大（从1开始数）和第(m+n)/2+1大（从1开始数）的数的算术平均值。

那么如何判断两个有序数组A,B中第k大的数呢？

我们需要判断A[k/2-1]和B[k/2-1]的大小。

如果A[k/2-1]==B[k/2-1]，那么这个数就是两个数组中第k大的数。

如果A[k/2-1]<B[k/2-1], 那么说明A[0]到A[k/2-1]都不可能是第k大的数，所以需要舍弃这一半，继续从A[k/2]到A[A.length-1]继续找。当然，因为这里舍弃了A[0]到A[k/2-1]这k/2个数，那么第k大也就变成了，第k-k/2个大的数了。

如果 A[k/2-1]>B[k/2-1]，就做之前对称的操作就好。

 这样整个问题就迎刃而解了。

当然，边界条件页不能少，需要判断是否有一个数组长度为0，以及k==1时候的情况。

因为除法是向下取整，并且页为了方便起见，对每个数组的分半操作采取：

int partA = Math.min(k/2,m);
int partB = k - partA; 

 为了能保证上面的分半操作正确，需要保证A数组的长度小于B数组的长度。
总的时间复杂度为O(logk),空间复杂度也是O(logk)，即为递归栈大小。在这个题目中因为k=(m+n)/2,所以复杂度是O(log(m+n))。

同时，在返回结果时候，注意精度问题，返回double型的就好。 

public class Solution {
    public double findMedianSortedArrays(int A[], int B[]) {
        int m = A.length;
        int n = B.length;
        if ((m + n) % 2 ==1 ){
            return helper(A, 0, m - 1, B, 0, n - 1, (m + n) / 2 + 1);//k传得是第k个，index实则k-1
        } else {
            return (helper(A, 0, m - 1, B, 0, n - 1, (m + n) / 2 + 1) + helper(A, 0, m - 1, B, 0, n - 1, (m + n) / 2)) / 2.0;
        }
    }
    public int helper(int A[], int i, int i0, int B[], int j, int j0, int k){
        int a = i0 - i + 1;// x现有的A数组长度
        int b = j0 - j + 1;
        if (a > b){ // 如果A数组比B数组长 反过来比较
            return helper(B, j, j0, A, i, i0, k);
        }
        if (a == 0){ //当A数组的值全部比较完的时候
            return B[j + k -  1];//此时的k与原来的k相比已经删除了A的长度 
                                //-1是因为index要-1
        }
        if (k == 1){//此时必须要退出 因为k==1时候已经无法再往下分
            return Math.min(A[i], B[j]);
        }
        int posA = Math.min(k/2, a);//防止此时k/2溢出
        int posB = k - posA;
        if (A[posA + i -1] == B[posB + j - 1]){// 如果相等 则中心元素就为次相等值
            return A[posA + i - 1];
        } else if(A[posA + i -1] > B[posB + j - 1]){
            return helper(A, i, i0, B, posB + j, j0, k - posB);//删除前posB个元素
        } else{
            return helper(A, posA + i, i0, B, j, j0, k - posA);
        }
    }
}