Contents

1. 1. 题意：
2. 2. 方法一：
3. 3. 方法二：

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)).

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))

方法一：

合并两个数组，然后找中位数，O(n + m)

public double solve(int A[], int m, int B[], int n){

	vector<int> vec;  
	int pa = 0, pb = 0;

	while(pa < m  || pb < n){
		if (A[pa] >= B[pb]){
            vec.push_back(B[pb++]);  
		}else{
            vec.push_back(A[pa++]);  
		}
	}
	while(pa < m){
		vec.push_back(A[pa++]);  
	}
	while(pb < n){
		vec.push_back(A[pb++]);  
	}

	if ((n+m) & 1){
        return vec[(n+m)/2];  
	}else{
        return (vec[(n+m)/2 - 1] + vec[(n+m)/2]) / 2.0;  
	}
}

方法二：

要求复杂度O(log(m+n))容易联想到用二分的思路去做，然后转化为去求两个有序数组中的第 K 大数。

public class Solution {

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        //两个数组合起来的总长度
        int k = m + n;
        
        if((k & 1) == 1){//分奇偶的情况
            return find(nums1, 0, m, nums2, 0, n, k/2 + 1);
        }else{
            return (find(nums1, 0, m, nums2, 0, n, k/2) + find(nums1, 0, m, nums2, 0, n, k/2 + 1)) / 2;
        }
    }

    //总的思路：
    //将求总数组的中位数改为求第k大数
    //首先假设数组A和B的元素个数都大于k/2，我们比较A[k/2-1]和B[k/2-1]两个元素，这两个元素分别表示A的第k/2小的元素和B的第k/2小的元素。这两个元素比较共有三种情况：>、<和=。
    //如果A[k/2-1] < B[k/2-1]，这表示A[0]到A[k/2-1]的元素都在A和B合并之后的前k小的元素前面。换句话说，A[k/2-1]不可能大于两数组合并之后的第k小值，所以我们可以将a数组的前k/2个
    //抛弃。改为求修改后的总数组的第k-k/2大数。 
    //同理，A[k/2-1] < B[k/2-1]时，将B后前k/2个数抛弃掉，改为求修改后的总数组的第k-k/2大数。 
    //A[k/2-1] = B[k/2-1]时，则合并后的数组的第k大的数已经找到,这里其实有个细节处理，实际上是k/2 和 k - k/2

    //加上边界处理
    //将求总数组的中位数改为求第k大数，从a数组中找第pa=min((k/2）, aEnd)大数与b数组中的第pb=k-pa大数比较
    //如果b中的大些则将a数组的前pa段去掉，改为求总数组的第k—pa大数
    //如果a中的大些则将b数组的后pb段去掉，改为求总数组的第k-pb大数

    //递归算法，不断缩小两个数组的范围，同时k的值也做出相应改变
    public double find(int[] A, int aStart, int aEnd, int[] B, int bStart, int bEnd,int kth){

    //统一将长度短的放置于find函数参数的前面项
        if(aEnd>bEnd) 
            return find(B, bStart, bEnd, A, aStart, aEnd, kth);
        
    //长度短的为空，则答案等同于求另外一个数组的第k大数
        if(aEnd<=0) 
            return B[bStart + kth -1];
        
    //递归到终点，两个数组的aStart和bStart已经到了中位数的位置
        if(kth==1)
            return min(A[aStart],B[bStart]);
        
        int pa = min(kth/2,aEnd), pb = kth-pa;
        
        if(A[aStart + pa-1] < B[bStart +pb -1]){
            return find(A, aStart+pa, aEnd-pa, B, bStart, bEnd, kth-pa );
        }else{
            return find(A, aStart, aEnd, B, bStart + pb, bEnd - pb,kth-pb);
        }
    }

    public int min(int a, int b){
        return a>b?b:a;
    }
}