Leetcode4. Median of Two Sorted Arrays

ddddLeetcode刷题

• Author：李英民 | Henry
• E-mail: li_yingmin@outlookdotcom
• $Beijing~~U~of~Posts~and~Telecom$$(BUPT~)$
• Home: https://liyingmin.wixsite.com/henry

• 快速了解我: About Me

• 转载请保留上述引用内容，谢谢配合！

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

我的代码1：时间复杂度O(nlogn)~O(n^2),空间复杂度O(n)

//Author: Li-Yingmin@https://liyingmin.wixsite.com/henry
//Email: li_yingmin@outlook.com
//Leetcode-4
//T(n)=O(nlogn)~O(n^2), S(n)=O(n)
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        if(0 == nums1.size() + nums2.size()) return -1;
        nums1.insert(nums1.end(),nums2.begin(),nums2.end());
        sort(nums1.begin(),nums1.end());//排序，时间复杂度高，代价昂贵
        if(nums1.size() % 2 != 0)//奇数
            return nums1[nums1.size()/2];
        else return (nums1[nums1.size()/2] + nums1[nums1.size()/2 - 1])/2.0;
    }
};

我的代码2：时间复杂度O(k)~O(m+n),空间O(1)

//Author: Li-Yingmin@https://liyingmin.wixsite.com/henry
//Email: li_yingmin@outlook.com
//Leetcode-4
//T(n)=O(k)~O(m+n), S(n)=O(1)
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        auto midsize = (nums1.size() + nums2.size()) / 2;
        decltype(nums1.size()) temp = 0;//游标
        int value = 0;
        int medianL = 0;
        int medianR = 0;
        auto vit1 = nums1.begin();
        auto vit2 = nums2.begin();
        while(vit1 != nums1.end() || vit2 != nums2.end())
        { 
            if(vit2 == nums2.end() || (vit1 != nums1.end() && *vit1 <= *vit2))
            {
                value = *vit1;
                ++vit1;
            }
            else 
            {
                value = *vit2;
                ++vit2;
            }
            if(midsize != 0 && temp == midsize - 1)//如果midsize=0，这里不安全
                medianL = value;
            if(temp == midsize)
            {
                medianR = value;
                break;
            }
            ++temp;
        }
        if((nums1.size() + nums2.size()) % 2 != 0) return medianR;
        else return (medianL + medianR)/2.0;
    }
};

• if(vit2 == nums2.end() || (vit1 != nums1.end() && *vit1 <= *vit2))
• • 这里的顺序非常重要，先判断vit2是否指向尾后，然后vit1是否尾后，最后才解引用
• • 这里的逻辑好好理解，首先，如果vit2 == nums2.end()，直接移动vit1
• • 剩下的就是vit2没有指向尾后：
• • • 判断vit1是否指向尾后，如果指向尾后，转向else语句，移动vit2
• • • 如果vit1没有指向尾后，这时，vit1和vit2都可用，判断 *vit1 <= *vit2
• • • 若*vit1 <= *vit2成立，移动vit1，反之移动vit2

• temp放在靠后的位置是因为，把temp当做下标来使用，因此判断与midsize的大小前，temp还不应该++。可以用temp=0，m=1，n=1的时候来思考。此时，midsize = 1。

• 
• 建议，不要用个数来考虑数组，一致使用下标，因为这样可以直接使用[]，只是需要注意靠近0的时候，下标是否有意义。

优秀代码：时间复杂度O(log(m+n))，空间O(1)?