【Leetcode】寻找两个有序数组的中位数

 

使用二分法搜寻合适的i值，计算对应的j值，最后通过分类讨论nums1和nums2的多种情况计算得到中值。

二分法的关键思想是   假设该数组的长度是N那么二分后是N/2，再二分后是N/4……直到二分到1结束（当然这是属于最坏的情况了，即每次找到的那个中点数都不是我们要找的），那么二分的次数就是基本语句执行的次数，于是我们可以设次数为x，N*（1/2）^x=1；则x=logn,底数是2。

因此，该问题的时间复杂度是 O(log(min(m,n)).

空间复杂度 O(m+n)

执行用时 :  300ms, 在Median of Two Sorted Arrays的C++提交中击败了7.57% 的用户

内存消耗 :  11 MB, 在Median of Two Sorted Arrays的C++提交中击败了77.28% 的用户

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        double ans;
        int len1 = nums1.size();
        int len2 = nums2.size();
        if (len1 > len2){
            vector<int> temp(nums1);
            nums1 = nums2;
            nums2 = temp;
            len1 = nums1.size();
            len2 = nums2.size();
        }
        
        // if nums1 is empty 
        if (len1 == 0){
            if (len2 % 2 == 0)
                return ans = 0.5*(nums2[len2/2 - 1] + nums2[len2/2]);
            else
                return ans = nums2[int(len2/2)];
        }
        
        int i = 0, j = 0;
        int imin = 0, imax = len1; // 这两个变量用于二分法
        
        while(imin <= imax){  // 二分法的开展条件
            i = int(0.5*(imin+imax));
            j = getValueJ(len1,len2,i);
            
            if(i==0 || j==len2 || nums1[i-1] <= nums2[j]){
                if(i==len1 || j==0 || nums1[i] >= nums2[j-1]){
                    ans = getMedian(nums1, nums2, len1, len2, i, j);
                    break;
                }
                else{
                    imin = i+1;
                    cout << "imin : " << imin << endl;
                }
            }
            else{
                imax = i;
            }
        }
        return ans;
    }
    
    int getValueJ(int len1, int len2, int iIndex){
        int jIndex;
        if ((len1+len2) % 2 == 0)
            jIndex = 0.5*(len1+len2) - iIndex;
        else
            jIndex = 0.5*(len1+len2+1) - iIndex;
        
        return jIndex;
    }
    
    double getMedian(vector<int> &num1, vector<int> &num2, int len1, int len2, int iIndex, int jIndex){
        
        /*********
        for (int i = 0; i < len1; i++)
            cout << num1[i] << " ";
        cout << endl;
        for (int j = 0; j < len2; j++)
            cout << num2[j] << " ";
        cout << endl;
        
        cout << "iIndex : "<< iIndex << endl;
        cout << "jIndex : "<< jIndex << endl;
        
        cout << "len1 : " << len1 << endl;
        cout << "len2 : " << len2 << endl;
        **********/        

        double median;
        vector<int> leftP, rightP;
        
        if ((len1+len2) % 2 ){
            cout << "the sum of two vector is odd number" << endl;
            
            // we know that size of vector leftP is bigger than that of vector rightP
            if (iIndex > 0 && jIndex > 0){
                vector<int> tmp;
                for (int i = 0; i < iIndex; i++)
                    tmp.push_back(num1[i]);
                for (int j = 0; j < jIndex; j++)
                    tmp.push_back(num2[j]);
                median =  *max_element(tmp.begin(), tmp.end());
            }
            else if (iIndex == 0)
                median = *max_element(num2.begin(), (num2.end()-(len2-jIndex)));
            else if (jIndex == 0)
                median = *max_element(num1.begin(), (num1.end()-(len1-iIndex)));

        }
        
        else{
            cout << "the sum of two vector is even number" << endl;
            
            if (iIndex == 0){
                leftP.clear();
                rightP.clear();
                for (int j = 0; j < jIndex; j++){
                    leftP.push_back(num2[j]);
                }
                
                rightP = num1;
                if(jIndex < len2)
                    for(int j = jIndex; j < len2; j++)
                        rightP.push_back(num2[j]);
                
                /**************
                cout << "leftP : ";
                for(int i = 0; i < leftP.size(); i++)
                    cout << leftP[i] << " ";
                cout << endl << "rightP : ";
                for(int j = 0; j < rightP.size(); j++)
                    cout << rightP[j] << "";
                cout << endl;
                **************/
            }
            
            else if (iIndex == len1){
                leftP.clear();
                rightP.clear();
                leftP = num1;
                if (jIndex > 0 && jIndex < len2)
                    for (int j = 0; j < jIndex; j++)
                        leftP.push_back(num2[j]);
                
                for (int j = jIndex; j < len2; j++)
                    rightP.push_back(num2[j]);
            }
            
            else{
                leftP.clear();
                rightP.clear();
                for (int i = 0; i < iIndex; i++)
                    leftP.push_back(num1[i]);
                
                if(jIndex > 0){
                    for(int j = 0; j < jIndex; j++)
                        leftP.push_back(num2[j]);
                }
                
                for(int i = iIndex; i < len1; i++)
                    rightP.push_back(num1[i]);
                
                if(jIndex < len2)
                    for(int j = jIndex; j < len2; j++)
                        rightP.push_back(num2[j]);
            }
            
            int leftV =  *max_element(leftP.begin(), leftP.end());
            int rightV = *min_element(rightP.begin(), rightP.end());
            cout << "leftV : " << leftV << "  " << "rightV : " << rightV << endl;
            median = 0.5*(leftV+rightV);                        
        }
        return median;
    }
};

 

nums1和nums2都是按升序排列，其长度size = m+n。将前 size/2+1(size为偶数) 或 (size+1)/2(size为奇数) 进行排序，即可找到中位数。

Tip: 学习迭代器的使用，迭代器的增长；

执行用时 :  32 ms, 在Median of Two Sorted Arrays的C++提交中击败了98.57% 的用户

内存消耗 :  9.7 MB, 在Median of Two Sorted Arrays的C++提交中击败了87.28% 的用户

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        
        auto left = nums1.begin();
        auto right = nums2.begin();
        int size = nums1.size() + nums2.size();
        //int sum = 0;
        int temp = 0; 
        int temp1 = 0;
        for (int i = 0; i <= size / 2; i++)
        {    
            if (left == nums1.end())
                temp = *right++;
            else if (right == nums2.end())
                temp = *left++;
            else if (*left < *right)
                temp = *left++;
            else
                temp = *right++;
            if (size / 2 - 1 == i)
            {
                temp1 = temp;
            }
        }
        if (size % 2 != 0)
        {
            return temp;
        }
        else
        {
            return (temp + temp1) / 2.0;
        }

    }
};