給定兩個大小分別為?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
O(m+n)復雜度的方法
class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int l1 = 0, l2 = 0, mid1, mid2;int r1 = nums1.size() - 1, r2 = nums2.size() - 1;int total = nums1.size() + nums2.size();bool is_odd = total % 2;int mid = total / 2;double result = 0.0;// 如果 nums1 為空if (nums1.empty()) {if (nums2.empty()) return 0.0; // 兩個都空if (is_odd) return nums2[mid];return (nums2[mid - 1] + nums2[mid]) / 2.0;}// 如果 nums2 為空if (nums2.empty()) {if (is_odd) return nums1[mid];return (nums1[mid - 1] + nums1[mid]) / 2.0;}// 合并兩個數組（直接模擬合并直到中位數）int i = 0, j = 0, count = 0;int prev = 0, curr = 0;while (count <= mid) {prev = curr;if (i < nums1.size() && (j >= nums2.size() || nums1[i] <= nums2[j])) {curr = nums1[i++];} else {curr = nums2[j++];}count++;}if (is_odd) return curr;return (prev + curr) / 2.0;}
};
O(LogMin(M，N))的方法
class Solution {
public:int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {int index1 = 0, index2 = 0;int n1 = nums1.size(), n2 = nums2.size();while (true) {// 特殊情況：nums1已經用完了if (index1 == n1) return nums2[index2 + k - 1];if (index2 == n2) return nums1[index1 + k - 1];// 如果只要第1小的數，直接比較兩邊頭部if (k == 1) return min(nums1[index1], nums2[index2]);// 正常處理int half = k / 2;// 計算每個數組跳多少步int newIndex1 = min(index1 + half, n1) - 1;int newIndex2 = min(index2 + half, n2) - 1;int pivot1 = nums1[newIndex1];int pivot2 = nums2[newIndex2];// 誰的 pivot 小，誰的前面都不可能是第k小，全部丟掉if (pivot1 <= pivot2) {k -= (newIndex1 - index1 + 1);index1 = newIndex1 + 1;} else {k -= (newIndex2 - index2 + 1);index2 = newIndex2 + 1;}}}double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int total = nums1.size() + nums2.size();// 奇數情況，找第 (n/2 + 1) 小if (total % 2 == 1) {return getKthElement(nums1, nums2, total / 2 + 1);} // 偶數情況，取中間兩個平均else {return (getKthElement(nums1, nums2, total / 2) +getKthElement(nums1, nums2, total / 2 + 1)) / 2.0;}}
};
