//
//  Solution4.hpp
//  Algorithm
//
//  Created by Pancf on 2019/11/24.
//  Copyright © 2019 Pancf. All rights reserved.
//

#ifndef Solution4_hpp
#define Solution4_hpp

#include <stdio.h>
#include <vector>

using std::vector;

class Solution4 {
/**
 难度：Hard
 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)).

 You may assume nums1 and nums2 cannot be both empty.

 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
 ================================================================================================
 Accept details:
 Runtime: 16 ms, faster than 90.77% of C++ online submissions for Median of Two Sorted Arrays.
 Memory Usage: 10.3 MB, less than 30.93% of C++ online submissions for Median of Two Sorted Arrays.
 思路:求两个数组的中位数，o(log(m+n))复杂度，其实归并排序刚好就是这个复杂度。所以直接归并再取合并后的数组中位数即可。
 但是这样做会多花掉一些空间以及时间，因为归并数组增长到 (m+n)/2 + 1长度时，其实已经没有必要继续了。若m+n是奇数，
 那么中间值其实就是归并数组的第(m+n)/2 + 1个数字；若m+n是偶数，那么中间值就是最后两个数字的平均值。
 从结果来看耗时在我的预期内，但暂时没想明白memory usage为什么这么多。
 */
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2);
    
    static void test() {
        vector<int> nums1 = vector<int>{1, 2};
        vector<int> nums2 = vector<int>{3, 4};
        Solution4 s = Solution4();
        printf("%f", s.findMedianSortedArrays(nums1, nums2));
    }
};

#endif /* Solution4_hpp */