4. 寻找两个正序数组的中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

算法的时间复杂度应该为 O(log (m+n)) 。

示例 1：

输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2

示例 2：

输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
 

提示：

nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

自己写的：

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {nums1.insert(nums1.end(),nums2.begin(),nums2.end());sort(nums1.begin(),nums1.end());if(nums1.size()%2){return nums1.at(nums1.size()/2);}else{return (double(nums1.at(nums1.size()/2))+double(nums1.at(nums1.size()/2-1)))/2;}}
};

示例模板：

class Solution {
public:double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2) {int size = (int) (nums1.size() + nums2.size());int dst = size / 2;bool need_ave = size % 2 == 0;int *arr = new int[size];int index = 0;double result = 0;auto iter = nums1.begin();for (auto num: nums2) {for (; iter != nums1.end();) {if (num <= *iter) {arr[index] = num;if (index == dst) {result = need_ave ? (double) (arr[index - 1] + arr[index]) / 2 : arr[index];return result;}index++;break;} else {arr[index] = *iter;if (index == dst) {result = need_ave ? (double) (arr[index - 1] + arr[index]) / 2 : arr[index];return result;}index++;iter++;}}if (iter == nums1.end()) {arr[index] = num;if (index == dst) {result = need_ave ? (double) (arr[index - 1] + arr[index]) / 2 : arr[index];return result;}index++;}}for (; iter != nums1.end(); iter++) {arr[index] = *iter;if (index == dst) {result = need_ave ? (double) (arr[index - 1] + arr[index]) / 2 : arr[index];return result;}index++;}delete[]arr;return result;}
};

效率：