Median of Two Sorted Arrays(计算两个数组的中数)

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

思路：先判断两数组是否为空，对两个数组设置比较下标left、right，循环比较两下标对应的数组值，将小者放入新的数组res中，移动下标。当一个数组下标到末尾时将另一个数组中未进行对比的所有元素直接拷贝进新的数组。最后找到两数组的中数就比较简单了。注意这种方法的时间复杂度为O(m+n),

class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int left = 0; int right = 0; vector<int> res; int n = nums1.size() + nums2.size(); if(nums1.empty() && !nums2.empty()) if(n%2 == 0) return (nums2[n/2 - 1] + nums2[n/2]) / 2.0; else return float(nums2[n/2]); if(!nums1.empty() && nums2.empty()) if(n%2 == 0) return (nums1[n/2 - 1] + nums1[n/2]) / 2.0; else return float(nums1[n/2]); while(left < (int)(nums1.size()) && right < (int)(nums2.size())){ if(nums1[left] < nums2[right]){ res.push_back(nums1[left]); left = left + 1 ; } else{ res.push_back(nums2[right]); right = right + 1; } } for(int i=left;i<(int)nums1.size();i++){ res.push_back(nums1[i]); } for(int i=right;i<(int)nums2.size();i++){ res.push_back(nums2[i]); } if(n % 2 == 0) return (res[n/2 - 1] + res[n/2]) / 2.0; else return float(res[n/2]); } };

优化：当然，可以先计算中间元素所在的位置，直接比较两数组中元素值（不用另外的新数组），当while循环到中间位置时，输出该元素值（或通过计算当前元素与前一个元素和的平均值（总元素个数为偶数时）），这样同时降低了算法的时间和空间复杂度。

bool oddLength = ((int)(nums1.size() + nums2.size()) % 2) != 0; int medianLocation = ((int)(nums1.size() + nums2.size()) / 2) + 1; int i=0; int j=0; int indexCount=0; int current =0; int prev= 0; while(i!=(int)nums1.size() || j!=(int)nums2.size()) { prev = current; if(i!=(int)nums1.size() && j!=(int)nums2.size()) { current = min(nums1[i],nums2[j]); if(current == nums1[i]) i++; else j++; } else { if(i==(int)nums1.size()) current = nums2[j++]; else current = nums1[i++]; } indexCount++; if(indexCount==medianLocation) return oddLength? current : ((double)(current+prev))/2; } return 0;