題目描述

給定兩個大小為 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

方法一：暴力解法

直接將兩個數組賦值到一個新數組中，然后排序。

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int n1=nums1.size(),n2=nums2.size();vector<int> nums3;for(int i=0;i<n1;i++) nums3.push_back(nums1[i]);for(int i=0;i<n2;i++) nums3.push_back(nums2[i]);sort(nums3.begin(),nums3.end());int s=(n1+n2)/2;double res;if((n1+n2)%2) res=1.0*nums3[s];else res=1.0*(nums3[s]+nums3[s-1])/2;return res;}
};

復雜度分析：

• 兩個有序數組合并最快的方法，時間復雜度: O((m + n)log(m+ n)), 這里m和n分別為數組nums1和nums2的長度，

• 空間復雜度: O(m+ n),存儲合并以后的數組，需要m+ n這么多空間。
  

方法二：二分查找

（注：此方法來自于力扣官方題解）

class Solution {
public:int getKthElement(const vector<int>& nums1, const vector<int>& nums2, int k) {/* 主要思路：要找到第 k (k>1) 小的元素，那么就取 pivot1 = nums1[k/2-1] 和 pivot2 = nums2[k/2-1] 進行比較* 這里的 "/" 表示整除* nums1 中小于等于 pivot1 的元素有 nums1[0 .. k/2-2] 共計 k/2-1 個* nums2 中小于等于 pivot2 的元素有 nums2[0 .. k/2-2] 共計 k/2-1 個* 取 pivot = min(pivot1, pivot2)，兩個數組中小于等于 pivot 的元素共計不會超過 (k/2-1) + (k/2-1) <= k-2 個* 這樣 pivot 本身最大也只能是第 k-1 小的元素* 如果 pivot = pivot1，那么 nums1[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "刪除"，剩下的作為新的 nums1 數組* 如果 pivot = pivot2，那么 nums2[0 .. k/2-1] 都不可能是第 k 小的元素。把這些元素全部 "刪除"，剩下的作為新的 nums2 數組* 由于我們 "刪除" 了一些元素（這些元素都比第 k 小的元素要小），因此需要修改 k 的值，減去刪除的數的個數*/int m = nums1.size();int n = nums2.size();int index1 = 0, index2 = 0;while (true) {// 邊界情況if (index1 == m) {return nums2[index2 + k - 1];}if (index2 == n) {return nums1[index1 + k - 1];}if (k == 1) {return min(nums1[index1], nums2[index2]);}// 正常情況int newIndex1 = min(index1 + k / 2 - 1, m - 1);int newIndex2 = min(index2 + k / 2 - 1, n - 1);int pivot1 = nums1[newIndex1];int pivot2 = nums2[newIndex2];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 totalLength = nums1.size() + nums2.size();if (totalLength % 2 == 1) {return getKthElement(nums1, nums2, (totalLength + 1) / 2);}else {return (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;}}
};

復雜度分析

• 時間復雜度：O(log(m+n))，其中 m 和 n 分別是數組 nums1 和 nums2 的長度。初始時有 k=(m+n)/2 或k=(m+n)/2+1，每一輪循環可以將查找范圍減少一半，因此時間復雜度是O(log(m+n))。

• 空間復雜度：O(1)。