4_Median of Two Sorted Arrays.txt

/*********************************************************************************
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（m+n)，2080个样例的运行时间为65ms
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int num = nums1.size() + nums2.size();
        double mid = 0;
        int s1 = 0,s2 = 0, e1 = nums1.size() - 1, e2 = nums2.size() - 1;
        while(s1 <= e1){
            mid += nums1[s1++];
        }
        while(s2 <= e2){
            mid += nums2[s2++];
        }
        s1 = s2 = 0;
        while(num > 2){
            if(s1 <= e1 && s2 <= e2){
                if(nums1[s1] < nums2[s2]){
                    mid -= nums1[s1++];
                }else{
                    mid -= nums2[s2++];
                }
                if(nums1[e1] < nums2[e2]){
                    mid -= nums2[e2--];
                }else{
                    mid -= nums1[e1--];
                }    
            }else if(s1 > e1){
                mid -= nums2[e2--];
                mid -= nums2[s2++];
            }else{
                mid -= nums1[e1--];
                mid -= nums1[s1++];
            }
            num -= 2;
        }
        return mid/num;
        
    }
};

//在leetcode论坛上，有一个寻找第k大的值的算法，该算法的运行时间复杂度为O（log(m+n)),2080个样例的运行时间最快为32ms（不稳定）
class Solution {
public:
    //get the kth number of two sorted array
    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 == 0)
            return b[k-1];
        if(k == 1)
            return min(*a,*b);

        int pa = min(k/2,m),pb = k - pa;
        if(*(a + pa - 1) < *(b + pb -1))
            return findkth(a+pa,m-pa,b,n,k-pa);
        else if(*(a + pa -1) > *(b + pb -1))
            return findkth(a,m,b+pb,n-pb,k-pb);
        else
            return *(a+pa-1);
    }
    
    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 & 0x1)
            return findkth(a,nums1.size(),
                           b,nums2.size(),
                           total/2+1);
        else
            return (findkth(a,nums1.size(),
                           b,nums2.size(),
                           total/2) +
                    findkth(a,nums1.size(),
                            b,nums2.size(),
                            total/2 + 1))/2;
    }
};