【leetcode】之Median of Two Sorted Arrays

問題描述：

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

我的解題思路：

拿到這道題目，最簡單的思路就是直接采用歸并排序中的merge算法，就可以在O(m+n)的時間複雜度内完成排序，然後可以在O(1)的時間内找到第[(m+n)/2]大的數，但是題目要求的複雜度是O(log(m+n))，是以自然需要思考優化政策。

比較容易想到的優化政策是：不對整個數組進行排序，而是把目标鎖定在尋找最小的[(m+n)/2]個數。可以設定兩個指針，分别指向兩個數組，然後進行周遊，直至找到[(m+n)/2]個數，這種做法的複雜度還是O(m+n)，依然不符合要求。

然後就是思考如何做到O(log(m+n))，因為有log的存在，就自然可以往分治遞歸，二叉樹（如最大最小堆），二分法上面去想。到這裡為止，我的思路大體都是對的。但是下一步我的思路就出問題了。我嘗試利用分治遞歸的思想，把原問題化成子問題，但是我一直在想着對兩個數組直接取中值進行劃分，然後再進行後續的操作。這種劃分子問題的方法是行不通的。之後是看了參考資料

http://blog.csdn.net/yutianzuijin/article/details/11499917/

才想明白劃分子問題的方法，具體的内容這份部落格講的很多好了，我就隻貼一下程式：

class Solution  
{  
private:
    double findkth(vector<int>::iterator a,int m,
                vector<int>::iterator b,int n,
                int k)
    {
        if(m >  n)
            return findkth(b,n,a,m,k);
        if(m == )
            return b[k-];
        if(k == )
            return min(*a,*b);

        int pa = min(k/,m),pb = k - pa;
        if(*(a + pa - ) < *(b + pb -))
            return findkth(a+pa,m-pa,b,n,k-pa);
        else if(*(a + pa -) > *(b + pb -))
            return findkth(a,m,b+pb,n-pb,k-pb);
        else
            return *(a+pa-);
    }
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        vector<int>::iterator a = nums1.begin();
        vector<int>::iterator b = nums2.begin();
        int total = nums1.size() + nums2.size();

        // judge the total num of two arrays is odd or even
        if(total & )
            return findkth(a,nums1.size(),
                           b,nums2.size(),
                           total/+);
        else
            return (findkth(a,nums1.size(),
                           b,nums2.size(),
                           total/) +
                    findkth(a,nums1.size(),
                            b,nums2.size(),
                            total/ + ))/;
    }
};