給定兩個大小為 m 和 n 的有序數組 nums1 和 nums2。

請你找出這兩個有序數組的中位數，并且要求算法的時間復雜度為 O(log(m + n))。

如果不考慮復雜度的話這個題目很簡單：將兩個數組合并為一個數組，然后用冒泡排序算法將合并后的數組進行排序，然后用二分法找出中間的數，但是這個復雜度遠遠超過O(log(m + n))，因為光冒泡排序就是O（n^2）。今天在leetcode上看了半個小時，也沒有想明白大神的解法，明天去找國外的導師匯報完后回來繼續看，明天爭取解出來，然后著手寫自己國內的論文和做語音識別的仿真。堅持就是勝利。先粘貼過來大神的解法。

#include <stdio.h>
#include <vector>
using namespace std;

#define max(a,b) (((a) > (b)) ? (a) : (b))
#define min(a,b) (((a) < (b)) ? (a) : (b))

class Solution {
public:
?? ?double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
?? ??? ?int n = nums1.size();
?? ??? ?int m = nums2.size();

?? ??? ?if (n > m) ?//保證數組1一定最短
?? ??? ?{
?? ??? ??? ?return findMedianSortedArrays(nums2, nums1);
?? ??? ?}

?? ??? ?// Ci 為第i個數組的割,比如C1為2時表示第1個數組只有2個元素。LMaxi為第i個數組割后的左元素。RMini為第i個數組割后的右元素。
?? ??? ?int LMax1, LMax2, RMin1, RMin2, c1, c2, lo = 0, hi = 2 * n; ?//我們目前是虛擬加了'#'所以數組1是2*n長度

?? ??? ?while (lo <= hi) ? //二分
?? ??? ?{
?? ??? ??? ?c1 = (lo + hi) / 2; ?//c1是二分的結果
?? ??? ??? ?c2 = m + n - c1;

?? ??? ??? ?LMax1 = (c1 == 0) ? INT_MIN : nums1[(c1 - 1) / 2];
?? ??? ??? ?RMin1 = (c1 == 2 * n) ? INT_MAX : nums1[c1 / 2];
?? ??? ??? ?LMax2 = (c2 == 0) ? INT_MIN : nums2[(c2 - 1) / 2];
?? ??? ??? ?RMin2 = (c2 == 2 * m) ? INT_MAX : nums2[c2 / 2];

?? ??? ??? ?if (LMax1 > RMin2)
?? ??? ??? ??? ?hi = c1 - 1;
?? ??? ??? ?else if (LMax2 > RMin1)
?? ??? ??? ??? ?lo = c1 + 1;
?? ??? ??? ?else
?? ??? ??? ??? ?break;
?? ??? ?}
?? ??? ?return (max(LMax1, LMax2) + min(RMin1, RMin2)) / 2.0;
?? ?}
};

int main(int argc, char *argv[])
{
?? ?vector<int> nums1 = { 2,3, 5 };
?? ?vector<int> nums2 = { 1,4,7, 9 };
?? ?
?? ?Solution solution;
?? ?double ret = solution.findMedianSortedArrays(nums1, nums2);
?? ?return 0;
}

作者：bian-bian-xiong
鏈接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/4-xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu/
來源：力扣（LeetCode）。

總結

以上是生活随笔為你收集整理的C++leetcode找出两个有序数组的中位数（2）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。