Leetcode 4. Median of Two Sorted

这题想错了，复杂度并不符合要求囧

原题地址：https://leetcode.com/problems/median-of-two-sorted-arrays/description/

题目描述

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

在log(m+n)的时间复杂度内找出两个数组的中位数。数组元素总数是偶数的话取中间两个值的均值。

解题思路

分别为两个数组维护一个最大堆，计算出元素总数t，每次比较两个堆堆顶的元素大小，弹出较大的那个，进行(t-1)/2次这样的操作之后，再根据元素总个数的奇偶来返回适当的值，如果是奇数，只要取当前两个堆顶元素中较大的那个返回，如果是偶数，就要进行两次这样的操作然后求均值。全程都要注意某个数组的堆为空或者在过程中变空的情况。

代码

#include <algorithm>
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int total = nums1.size()+nums2.size();
        int mid = (total-1)/2;
        make_heap(nums1.begin(),nums1.end());
        make_heap(nums2.begin(),nums2.end());
        for(int i =0;i<mid;i++){
            if(nums1.empty()){
                pop_heap(nums2.begin(),nums2.end());
                nums2.pop_back();
            }else if(nums2.empty()){
                pop_heap(nums1.begin(),nums1.end());
                nums1.pop_back();                
            }else if(nums1.front()>=nums2.front()){
                pop_heap(nums1.begin(),nums1.end());
                nums1.pop_back();
            }else if(nums2.front()>nums1.front()){
                pop_heap(nums2.begin(),nums2.end());
                nums2.pop_back();
            }
        }
        if(total%2==0){
            int a,b;
            if(nums1.empty()){
                a=nums2.front();
                pop_heap(nums2.begin(),nums2.end());
                nums2.pop_back();
                b=nums2.front();
                return (double)(a+b)/2;
            }else if(nums2.empty()){
                a=nums1.front();
                pop_heap(nums1.begin(),nums1.end());
                nums1.pop_back();
                b=nums1.front();
                return (double)(a+b)/2;                
            }
            
            if(nums1.front()>=nums2.front()){
                a=nums1.front();
                pop_heap(nums1.begin(),nums1.end());
                nums1.pop_back();
            }else if(nums2.front()>nums1.front()){
                a=nums2.front();
                pop_heap(nums2.begin(),nums2.end());
                nums2.pop_back();                
            }
            
            if(nums1.empty()){
                b=nums2.front();
                return (double)(a+b)/2;
            }else if(nums2.empty()){
                b=nums1.front();
                return (double)(a+b)/2;
            }else if(nums1.front()>=nums2.front()){
                b=nums1.front();
                return (double)(a+b)/2;
            }else if(nums2.front()>nums1.front()){
                b=nums2.front();    
                return (double)(a+b)/2;
            }
        }else{
            if(nums1.empty()){
                return nums2.front();
            }
            if(nums2.empty()){
                return nums1.front();
            }
            return (nums1.front()>nums2.front()?nums1.front():nums2.front());  
        }
    }
};