題目

給定兩個(gè)大小為 m 和 n 的有序數(shù)組 nums1 和 nums2轩端。
請(qǐng)你找出這兩個(gè)有序數(shù)組的中位數(shù)帜慢，并且要求算法的時(shí)間復(fù)雜度為 O(log(m + n))瘦真。
你可以假設(shè) nums1和 nums2 不會(huì)同時(shí)為空绰播。

示例 1:

nums1 = [1, 3]
nums2 = [2]

則中位數(shù)是 2.0

示例 2:

nums1 = [1, 2]
nums2 = [3, 4]

則中位數(shù)是 (2 + 3)/2 = 2.5

題解

暴力法

其實(shí)這個(gè)方法是最容易想到的方法,把兩個(gè)有序數(shù)組合并成一個(gè)有序數(shù)組.然后直接找到中位數(shù).

實(shí)現(xiàn)代碼

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
    int allcount = nums1Size+ nums2Size;
    int z = allcount/2;
    int y = allcount%2;
    
    int numOneIndex = z;
    int numTwoIndex = y==1?z:z-1;
    int num1Index=0;
    int num2ndex=0;
    
    if (nums1Size==0) {
        return (nums2[numOneIndex]+nums2[numTwoIndex])/2.0;
    }
    if (nums2Size == 0) {
        return (nums1[numOneIndex]+nums1[numTwoIndex])/2.0;;
    }
    
    double result = 0.0;
    int * allNum = malloc(allcount * sizeof(int));
    
    do {
        if (nums1[num1Index]>nums2[num2ndex]) {
            allNum[num1Index+num2ndex]=nums2[num2ndex];
            num2ndex++;
        }else{
              allNum[num1Index+num2ndex]=nums1[num1Index];
              num1Index++;
            
        }
        if (num2ndex == nums2Size) {
            for (int i=num1Index; i<nums1Size; i++) {
                 allNum[num1Index+num2ndex]=nums1[num1Index];
                 num1Index++;
            }
            break;
        }
        if (num1Index == nums1Size) {
            for (int i=num2ndex; i<nums2Size; i++) {
                 allNum[num1Index+num2ndex]=nums2[num2ndex];
                 num2ndex++;
            }
            break;
        }
        
    } while (1);
    
    
    result=(allNum[numOneIndex]+allNum[numTwoIndex])/2.0;;
    free(allNum);
    return result;
}

復(fù)雜度分析

時(shí)間復(fù)雜度：
因?yàn)榘阉械臄?shù)都排列了一遍,因此時(shí)間復(fù)雜度是 O(m+n)
空間復(fù)雜度:
需要占用 m+n 內(nèi)存 .因此 空間復(fù)雜度也是O(m+n)

暴力法之直接找數(shù)

因?yàn)槭莾蓚€(gè)有序數(shù)組,因此我們可以直接查找一半數(shù)據(jù),將中位數(shù)解答出來.

實(shí)現(xiàn)代碼

double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
   int allcount = nums1Size+ nums2Size;
      int z = allcount/2;
      int y = allcount%2;
      
      int numOneIndex = z;
      int numTwoIndex = y==1?z:z-1;
      int num1Index=0;
      int num2ndex=0;
      int * temp = NULL;
   if (nums1Size==0) {
       return (nums2[numOneIndex]+nums2[numTwoIndex])/2.0;
   }
   if (nums2Size == 0) {
       return (nums1[numOneIndex]+nums1[numTwoIndex])/2.0;;
   }
   double result =0.0;
   int frontNum =0.0;
   int currentNum = 0.0;
   do {
         frontNum =currentNum;
       if (num2ndex==nums2Size) {
           currentNum=nums1[num1Index];
           temp=&num1Index;
       }else if (num1Index==nums1Size){
           currentNum=nums2[num2ndex];
            temp=&num2ndex;
       }else{
           if (nums1[num1Index]>nums2[num2ndex] ) {
               currentNum=nums2[num2ndex];
               temp=&num2ndex;
           }else{
                   currentNum=nums1[num1Index];
                   temp=&num1Index;
           }
       }

       if ((num1Index+num2ndex) == numOneIndex) {
           if (y==1) {
               result =(currentNum+currentNum)/2.0;
           }else{
               result =(currentNum + frontNum)/2.0;
           }
           break;
       }
       (*temp)++;
   } while (1);
        
     return result;
}

復(fù)雜度分析
時(shí)間復(fù)雜度：
因?yàn)橹檎伊艘话霐?shù)據(jù),因此時(shí)間復(fù)雜度是 O(m/2+n/2)
空間復(fù)雜度:
不需要開辟內(nèi)存 ,復(fù)雜度是O(1)

上述算法,其實(shí)時(shí)間復(fù)雜度并沒有比暴力法減少,反而增加了.這是因?yàn)?每次都進(jìn)行了變量之間的反復(fù)賦值導(dǎo)致時(shí)間增加.

遞歸法(官方解法翻譯)

為了解決這個(gè)問題花枫，我們需要理解 “中位數(shù)的作用是什么”刻盐。在統(tǒng)計(jì)中，中位數(shù)被用來：

將一個(gè)集合劃分為兩個(gè)長(zhǎng)度相等的子集劳翰，其中一個(gè)子集中的元素總是大于另一個(gè)子集中的元素敦锌。

如果理解了中位數(shù)的劃分作用，我們就很接近答案了佳簸。
首先乙墙，讓我們?cè)谌我晃恢?i 將 A 劃分成兩個(gè)部分：

                 left_A             |        right_A
    A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]

由于 A 中有m 個(gè)元素， 所以我們有 m+1 種劃分的方法（i=0～m）溺蕉。
我們知道：

len(left_A)=i,len(right_A)=m?i.
注意：當(dāng) i=0 時(shí)伶丐，left_A 為空集， 而當(dāng) i=m 時(shí), right_A 為空集疯特。

采用同樣的方式，我們?cè)谌我晃恢?j 將 B 劃分成兩個(gè)部分：

                  left_B            |        right_B
    B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

將 left_A 和 left_B 放入一個(gè)集合肛走，并將 right_A 和 right_B 放入另一個(gè)集合漓雅。 再把這兩個(gè)新的集合分別命名為left_part 和right_part：

               left_part          |        right_part
    A[0], A[1], ..., A[i-1]  |  A[i], A[i+1], ..., A[m-1]
    B[0], B[1], ..., B[j-1]  |  B[j], B[j+1], ..., B[n-1]

如果我們可以確認(rèn)：

• 1.len(left_part)=len(right_part)
• 2.max(left_part)≤min(right_part)

那么，我們已經(jīng)將 {A,B} 中的所有元素劃分為相同長(zhǎng)度的兩個(gè)部分朽色，且其中一部分中的元素總是大于另一部分中的元素邻吞。那么：

median =
?
要確保這兩個(gè)條件，我們只需要保證：

1. i+j=m?i+n?j（或：m?i+n?j+1）
   如果 n≥m葫男，只需要使 i=0～m, j=
2. B[j?1]≤A[i] 以及 A[i?1]≤B[j]

ps.1 為了簡(jiǎn)化分析抱冷，我假設(shè)
A[i?1],B[j?1],A[i],B[j] 總是存在，哪怕出現(xiàn) i=0,i=m, j=0,或是 j=n 這樣的臨界條件梢褐。我將在最后討論如何處理這些臨界值旺遮。

ps.2 為什么 n≥m？由于0≤i≤m 且 j= 盈咳，我必須確保 j 不是負(fù)數(shù)耿眉。如果 n<m，那么 j 將可能是負(fù)數(shù)鱼响，而這會(huì)造成錯(cuò)誤的答案鸣剪。(在 n≥m的時(shí)候,j一定不是負(fù)數(shù)的)

推導(dǎo)
i<m?j>0 以及 i>0?j<n 始終成立，這是因?yàn)椋?br> m≤n, i<m?j= >≥ ≥0
m≤n, i>0?j=<(\frac{2n+1}{2})$≤n

所以，我們需要做的是：

在 [0筐骇，m] 中搜索并找到目標(biāo)對(duì)象 i债鸡，以使：B[j?1]≤A[i] 且A[i?1]≤B[j], 其中 j=

接著，我們可以按照以下步驟來進(jìn)行二叉樹搜索：

• 1. 設(shè) imin=0铛纬，imax=m, 然后開始在 [imin,imax] 中進(jìn)行搜索娘锁。
• 2. 令 i=, j=
• 3. 現(xiàn)在我們有 len(left_part)=len(right_part)。 而且我們只會(huì)遇到三種情況：
• • B[j?1]≤A[i] 且 A[i?1]≤B[j]：
    這意味著我們找到了目標(biāo)對(duì)象 i饺鹃，所以可以停止搜索莫秆。
• • [j?1]>A[I]：
    這意味著 A[i] 太小，我們必須調(diào)整 i 以使 B[j?1]≤A[i]悔详。
    我們可以增大 i 嗎镊屎？
    是的，因?yàn)楫?dāng) i 被增大的時(shí)候茄螃，j 就會(huì)被減小缝驳。
    因此 B[j?1] 會(huì)減小，而 A[i] 會(huì)增大归苍，那么 B[j?1]≤A[i] 就可能被滿足用狱。
    我們可以減小 i 嗎？
    不行拼弃，因?yàn)楫?dāng) i 被減小的時(shí)候夏伊，j 就會(huì)被增大。
    因此 B[j?1] 會(huì)增大吻氧，而 A[i] 會(huì)減小溺忧，那么 B[j?1]≤A[i] 就可能不滿足。
    所以我們必須增大
    i盯孙。也就是說鲁森，我們必須將搜索范圍調(diào)整為 [i+1,imax]。
    因此振惰，設(shè) imin=i+1歌溉，并轉(zhuǎn)到步驟 2。
• • A[i?1]>B[j]：
    這意味著 A[i?1] 太大骑晶，我們必須減小 i 以使 A[i?1]≤B[j]痛垛。
    也就是說，我們必須將搜索范圍調(diào)整為 [imin,i?1]透罢。
    因此榜晦，設(shè) imax=i?1，并轉(zhuǎn)到步驟 2羽圃。

當(dāng)找到目標(biāo)對(duì)象 i 時(shí)乾胶，中位數(shù)為：

max(A[i?1],B[j?1]), 當(dāng) m+n 為奇數(shù)時(shí)
,當(dāng)m+n為偶數(shù)時(shí)

現(xiàn)在抖剿，讓我們來考慮這些臨界值 i=0,i=m,j=0,j=n，此時(shí) A[i?1],B[j?1],A[i],B[j] 可能不存在识窿。其實(shí)這種情況比你想象的要容易得多斩郎。

我們需要做的是確保 max(left_part)≤min(right_part)。 因此喻频，如果 i 和 j不是臨界值（這意味著 A[i?1],B[j?1],A[i],B[j] 全部存在）, 那么我們必須同時(shí)檢查 B[j?1]≤A[i] 以及
A[i?1]≤B[j] 是否成立缩宜。但是如果 A[i?1],B[j?1],A[i],B[j] 中部分不存在，那么我們只需要檢查這兩個(gè)條件中的一個(gè)（或不需要檢查）甥温。

舉個(gè)例子锻煌，如果 i=0，那么 A[i?1] 不存在姻蚓，我們就不需要檢查 A[i?1]≤B[j] 是否成立宋梧。
所以，我們需要做的是：

在 [0狰挡，m] 中搜索并找到目標(biāo)對(duì)象 i捂龄，以使：
(j=0 or i=m or B[j?1]≤A[i]) 或是(i=0 or j=n or A[i?1]≤B[j]),其中 j=

在循環(huán)搜索中，我們只會(huì)遇到三種情況：

1. (j=0 or i=m or B[j?1]≤A[i]) 或是 (i=0 or j=n or A[i?1]≤B[j])加叁，這意味著 i 是完美的倦沧，我們可以停止搜索。
2. j>0 and i<m and B[j?1]>A[i] 這意味著 i 太小它匕，我們必須增大它展融。
3. i>0 and j<n and A[i?1]>B[j] 這意味著 i 太大，我們必須減小它超凳。

實(shí)現(xiàn)代碼

#define SELFMAX(x,y) x>y?x:y
#define SELFMIN(x,y) x>y?y:x
//官方題解
double findMedianSortedArrays2(int* nums1, int nums1Size, int* nums2, int nums2Size){
    if (nums1Size > nums2Size) { // to ensure nums1Size<=nums2Size
        int*  temp = nums1; nums1 = nums2; nums2 = temp;
        int tmp = nums1Size; nums1Size = nums2Size; nums2Size = tmp;
    }
    int iMin = 0, iMax = nums1Size, halfLen = (nums1Size + nums2Size + 1) / 2;
    while (iMin <= iMax) {
        //找i中間
        int i = (iMin + iMax) / 2;
        int j = halfLen - i;
        //i 太小
        if (i < iMax && nums2[j-1] > nums1[i]){
            iMin = i + 1; // i is too small
        }
        else if (i > iMin && nums1[i-1] > nums2[j]) {
            iMax = i - 1; // i is too big
        }
        else { // i is perfect
            int maxLeft = 0;
            if (i == 0) { maxLeft = nums2[j-1]; }
            else if (j == 0) { maxLeft = nums1[i-1]; }
            
            else { maxLeft = SELFMAX(nums1[i-1], nums2[j-1]); }
            if ( (nums1Size + nums2Size) % 2 == 1 ) { return maxLeft; }

            int minRight = 0;
            if (i == nums1Size) { minRight = nums2[j]; }
            else if (j == nums2Size) { minRight = nums1[i]; }
            else { minRight = SELFMIN(nums2[j], nums1[i]); }

            return (maxLeft + minRight) / 2.0;
        }
    }
    return 0.0;
}

復(fù)雜度分析

時(shí)間復(fù)雜度：
O(log(min(m,n)))愈污，
首先，查找的區(qū)間是 [0,m]轮傍。
而該區(qū)間的長(zhǎng)度在每次循環(huán)之后都會(huì)減少為原來的一半。
所以首装，我們只需要執(zhí)行 log(m) 次循環(huán)创夜。由于我們?cè)诿看窝h(huán)中進(jìn)行常量次數(shù)的操作，所以時(shí)間復(fù)雜度為 O(log(m))仙逻。
由于 m≤n驰吓，所以時(shí)間復(fù)雜度是 O(log(min(m,n)))。
空間復(fù)雜度：O(1)
我們只需要恒定的內(nèi)存來存儲(chǔ) 9 個(gè)局部變量系奉， 所以空間復(fù)雜度為O(1)檬贰。

尋找兩個(gè)有序數(shù)組的中位數(shù)
github地址