4. 尋找兩個正序數組的中位數
1. 題目描述：
給定兩個大小為 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
示例 3：
輸入：nums1 = [0,0], nums2 = [0,0]
輸出：0.00000
示例 4：
輸入：nums1 = [], nums2 = [1]
輸出：1.00000
示例 5：
輸入：nums1 = [2], nums2 = []
輸出：2.00000
2. 解題思路
1. 使用歸併的方式，合併兩個有序數組，得到一個大的有序數組。大的有序數組的中間位置的元素，即為中位數。
2. 不需要合併兩個有序數組，只要找到中位數的位置即可。由於兩個數組的長度已知，因此中位數對應的兩個數組的下標之和也是已知的。維護兩個指針，初始時分別指向兩個數組的下標 00 的位置，每次將指向較小值的指針後移一位（如果一個指針已經到達數組末尾，則只需要移動另一個數組的指針），直到到達中位數的位置。
2.1 C++
1 class Solution { 2 public: 3 double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { 4 int n1 = nums1.size(), n2 = nums2.size(); 5 vector<int> obj; 6 double temp= 0.0; 7 int i = 0, j = 0; 8 while(i < n1 || j < n2){ 9 if(i != n1 && j != n2){ 10 if(nums1[i] <= nums2[j]){ 11 obj.push_back(nums1[i]); 12 i++; 13 }else{ 14 obj.push_back(nums2[j]); 15 j++; 16 } 17 }else if(i == n1){ 18 obj.push_back(nums2[j]); 19 j++; 20 }else if(j == n2){ 21 obj.push_back(nums1[i]); 22 i++; 23 } 24 } 25 int n = (n1 + n2) / 2; 26 if((n1 + n2) % 2 == 0){ 27 temp = (obj[n - 1] + obj[n]) / 2.0; 28 }else{ 29 temp = obj[n]; 30 } 31 return temp; 32 } 33 };
