leetcode 004 Median of Two Sorted Arrays解题报告

　　这是一道非常经典的题，题目原型为求第k小的数，中位数只是特殊情况，因此接下来都讨论原题情况。原解应该是这个CSDN1，我不知道为什么CSDN大神的具体证明都用英语写了，其实我觉得这部分才是最重要的，本来算法就很纠结了，再用英语过一遍更看不懂了。在我彻底看懂写完一遍之后发现了这个链接CSDN2，可能写的比我更好一点，如果看我的出现问题了可以看看他的。解题过程如下：

解题过程

　　最重要的是证明假设，如果A[k/2-1]<B[k/2-1]，那么第k小的数一定不在A[0]~A[k/2-1]中，这一段数列就可以被排除。

　　用反证法，那么就来看看如果第k小的数在A[0]~A[k/2-1]中会怎么样。首先在A中，有(k/2-1)个数比A[k/2-1]小（注意数组下标从0开始），而在B中，因为B[k/2-1]>A[k/2-1]，所以至多有(k/2-1)个数比A[k/2-1]小（至多达成的情况为B[k/2-2]=1)，与之前得到的至多有k-2个数比A[k/2-1]小矛盾。

　　所以假设成立。

　　这个证完之后再看算法就一目了然了，每次比较有三种结果：
　　1. A[k/2-1]>B[k/2-1] : 扔掉B[0]~B[k/2-1], k减掉扔掉的个数
　　2. A[k/2-1]<B[k/2-1] : 扔掉A[0]~A[k/2-1], k减掉扔掉的个数
　　3. A[k/2-1]=B[k/2-1] : 返回A[k/2-1]

　　边界情况：
　　1. 如果A或B为空，返回B[k-1]或A[k-1]，注意k在递归的时候的变化，k-1的原因是数组下标从0开始
　　2. 如果k=1，返回A[0]和B[0]中较小值
　　3. A[k/2-1]=B[k/2-1] : 返回A[k/2-1]

　　最上面的证明假设有一个重要的前提是假定A和B中的元素个数都大于等于k/2，如果A的数组元素个数比k/2要小应该怎么办呢？（如果B的比k/2要少就把A和B互换）

　　假定A数组有m个数，B数组有n个数，这时候我们就不再取第k/2个数，我们取第m个数，也就是A[m-1]，以及B[k-m-1]，这时候我们发现以上的证明仍然成立，仍然是m-1+k-m-1=k-2这个数字以及k+X，至此，所有的情况都考虑到了。

　　下面是我自己写的代码，写的比较丑陋，没有直接用int[]来的优雅（是的我就是用不来而已……）

c++代码

double find(vector<int> nums1,int pa,vector<int> nums2,int pb,int k){
    int n = nums1.size()-pa;
    int m = nums2.size()-pb;
    if (n>m)
        return find(nums2,pb,nums1,pa,k);
    if (n==0)
        return nums2[k-1+pb];
    if (m==0)
        return nums1[k-1+pa];
    if (k==1)
        return min(nums1[pa],nums2[pb]);
    int ka=min(k/2,n);
    int kb=k-ka;
    if (nums1[ka-1+pa]<nums2[kb-1+pb])
        return find(nums1,pa+ka,nums2,pb,k-ka);
    else if (nums1[ka-1+pa]>nums2[kb-1+pb])
        return find(nums1,pa,nums2,pb+kb,k-kb);
    else
        return (nums1[ka-1+pa]);
}
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n1,n2;
        n1 = nums1.size();
        n2 = nums2.size();
        if ((n1+n2)%2==1)
            return (find(nums1,0,nums2,0,(n1+n2)/2+1));
        else
            return ((find(nums1,0,nums2,0,(n1+n2)/2)+find(nums1,0,nums2,0,(n1+n2)/2+1))/2);
    }
};