這題想錯(cuò)了达舒，復(fù)雜度并不符合要求囧

原題地址：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)的時(shí)間復(fù)雜度內(nèi)找出兩個(gè)數(shù)組的中位數(shù)。數(shù)組元素總數(shù)是偶數(shù)的話取中間兩個(gè)值的均值。

解題思路

分別為兩個(gè)數(shù)組維護(hù)一個(gè)最大堆液样，計(jì)算出元素總數(shù)t，每次比較兩個(gè)堆堆頂?shù)脑卮笮⌒费荩瑥棾鲚^大的那個(gè)愤诱，進(jìn)行(t-1)/2次這樣的操作之后，再根據(jù)元素總個(gè)數(shù)的奇偶來返回適當(dāng)?shù)闹地はィ绻瞧鏀?shù)量愧，只要取當(dāng)前兩個(gè)堆頂元素中較大的那個(gè)返回，如果是偶數(shù)帅矗，就要進(jìn)行兩次這樣的操作然后求均值偎肃。全程都要注意某個(gè)數(shù)組的堆為空或者在過程中變空的情況。

代碼

#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());  
        }
    }
};