如何找出兩個排序數組的中位數

今天就跟大家聊聊有關如何找出兩個排序數組的中位數，可能很多人都不太了解，為了讓大家更加了解，小編給大家總結了以下內容，希望大家根據這篇文章可以有所收獲。

一、說明

     給定兩個大小為 m 和 n 的有序數組 nums1 和 nums2 。
     請找出這兩個有序數組的中位數。要求算法的時間復雜度為 O(log (m+n)) 。

     示例 1:

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

          中位數是 2.0

     示例 2:

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

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

二、解決方案參考

     1. Swift 語言

// 方式一
class Solution {
    func findMedianSortedArrays(nums1: [Int], _ nums2: [Int]) -> Double {
        let m = nums1.count
        let n = nums2.count
        
        if m > n {
            return findMedianSortedArrays(nums2, nums1)
        }

        var halfLength: Int = (m + n + 1) >> 1
        var b = 0, e = m
        var maxOfLeft = 0
        var minOfRight = 0
                
        while b <= e {
            let mid1 = (b + e) >> 1
            let mid2 = halfLength - mid1
            
            if mid1 > 0 && mid2 < n && nums1[mid1 - 1] > nums2[mid2] {
                e = mid1 - 1
            } else if mid2 > 0 && mid1 < m && nums1[mid1] < nums2[mid2 - 1] {
                b = mid1 + 1
            } else {
                if mid1 == 0 {
                    maxOfLeft = nums2[mid2 - 1]
                } else if mid2 == 0 {
                    maxOfLeft = nums1[mid1 - 1]
                } else {
                    maxOfLeft = max(nums1[mid1 - 1], nums2[mid2 - 1])
                }
                
                if (m + n) % 2 == 1 {
                    return Double(maxOfLeft)
                }
                
                if mid1 == m {
                    minOfRight = nums2[mid2]
                } else if mid2 == n {
                    minOfRight = nums1[mid1]
                } else {
                    minOfRight = min(nums1[mid1], nums2[mid2])
                }
                
                break
            }
        }
        return Double(maxOfLeft + minOfRight) / 2.0
    }
}

// 方式二
class MedianTwoSortedArrays {
    func findMedianSortedArrays(_ nums1: [Int], _ nums2: [Int]) -> Double {
        let m = nums1.count
        let n = nums2.count
        
        return (findKth(nums1, nums2, (m + n + 1) / 2) + findKth(nums1, nums2, (m + n + 2) / 2)) / 2
    }
    
    private func findKth(_ nums1: [Int], _ nums2: [Int], _ index: Int) -> Double {
        let m = nums1.count
        let n = nums2.count
        
        guard m <= n else {
            return findKth(nums2, nums1, index)
        }
        guard m != 0 else {
            return Double(nums2[index - 1])
        }
        guard index != 1 else {
            return Double(min(nums1[0], nums2[0]))
        }
        
        let i = min(index / 2, m)
        let j = min(index / 2, n)
        
        if nums1[i - 1] < nums2[j - 1] {
            return findKth(Array(nums1[i..<m]), nums2, index - i)
        } else {
            return findKth(nums1, Array(nums2[j..<n]), index - j)
        }
    }
}

     2. Python 語言

// 方式一
class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        a, b = sorted((nums1, nums2), key=len)
        m, n = len(a), len(b)
        after = (m + n - 1) / 2
        lo, hi = 0, m
        while lo < hi:
            i = (lo + hi) / 2
            if after-i-1 < 0 or a[i] >= b[after-i-1]:
                hi = i
            else:
                lo = i + 1
        i = lo
        nextfew = sorted(a[i:i+2] + b[after-i:after-i+2])
        return (nextfew[0] + nextfew[1 - (m+n)%2]) / 2.0

// 方式二
def median(A, B):
    m, n = len(A), len(B)
    if m > n:
        A, B, m, n = B, A, n, m
    if n == 0:
        raise ValueError

    imin, imax, half_len = 0, m, (m + n + 1) / 2
    while imin <= imax:
        i = (imin + imax) / 2
        j = half_len - i
        if i < m and B[j-1] > A[i]:
            # i is too small, must increase it
            imin = i + 1
        elif i > 0 and A[i-1] > B[j]:
            # i is too big, must decrease it
            imax = i - 1
        else:
            # i is perfect

            if i == 0: max_of_left = B[j-1]
            elif j == 0: max_of_left = A[i-1]
            else: max_of_left = max(A[i-1], B[j-1])

            if (m + n) % 2 == 1:
                return max_of_left

            if i == m: min_of_right = B[j]
            elif j == n: min_of_right = A[i]
            else: min_of_right = min(A[i], B[j])

            return (max_of_left + min_of_right) / 2.0

     3. Java 語言

class Solution {
    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length;
        int n = B.length;
        if (m > n) { // to ensure m<=n
            int[] temp = A; A = B; B = temp;
            int tmp = m; m = n; n = tmp;
        }
        int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
        while (iMin <= iMax) {
            int i = (iMin + iMax) / 2;
            int j = halfLen - i;
            if (i < iMax && B[j-1] > A[i]){
                iMin = iMin + 1; // i is too small
            }
            else if (i > iMin && A[i-1] > B[j]) {
                iMax = iMax - 1; // i is too big
            }
            else { // i is perfect
                int maxLeft = 0;
                if (i == 0) { maxLeft = B[j-1]; }
                else if (j == 0) { maxLeft = A[i-1]; }
                else { maxLeft = Math.max(A[i-1], B[j-1]); }
                if ( (m + n) % 2 == 1 ) { return maxLeft; }

                int minRight = 0;
                if (i == m) { minRight = B[j]; }
                else if (j == n) { minRight = A[i]; }
                else { minRight = Math.min(B[j], A[i]); }

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

     4. C++ 語言

#include <stdio.h>
// Classical binary search algorithm, but slightly different
// if cannot find the key, return the position where can insert the key 
int binarySearch(int A[], int low, int high, int key){
    while(low<=high){
        int mid = low + (high - low)/2;
        if (key == A[mid]) return mid;
        if (key > A[mid]){
            low = mid + 1;
        }else {
            high = mid -1;
        }
    }
    return low;
}
/tes:
// I feel the following methods is quite complicated, it should have a better high clear and readable solution
double findMedianSortedArrayHelper(int A[], int m, int B[], int n, int lowA, int highA, int lowB, int highB) {
    // Take the A[middle], search its position in B array
    int mid = lowA + (highA - lowA)/2;
    int pos = binarySearch(B, lowB, highB, A[mid]);
    int num = mid + pos;
    // If the A[middle] in B is B's middle place, then we can have the result
    if (num == (m+n)/2){
        // If two arrays total length is odd, just simply return the A[mid]
        // Why not return the B[pos] instead ? 
        //   suppose A={ 1,3,5 } B={ 2,4 }, then mid=1, pos=1
        //   suppose A={ 3,5 }   B={1,2,4}, then mid=0, pos=2
        //   suppose A={ 1,3,4,5 }   B={2}, then mid=1, pos=1
        // You can see, the `pos` is the place A[mid] can be inserted, so return A[mid]
        if ((m+n)%2==1){
            return A[mid];
        }
        
        // If tow arrys total length is even, then we have to find the next one.
        int next;
        // If both `mid` and `pos` are not the first postion.
        // Then, find max(A[mid-1], B[pos-1]). 
        // Because the `mid` is the second middle number, we need to find the first middle number
        // Be careful about the edge case
        if (mid>0 && pos>0){ 
            next = A[mid-1]>B[pos-1] ? A[mid-1] : B[pos-1];
        }else if(pos>0){
            next = B[pos-1];
        }else if(mid>0){
            next = A[mid-1];
        }
        
        return (A[mid] + next)/2.0;
    }
    // if A[mid] is in the left middle place of the whole two arrays
    //
    //         A(len=16)        B(len=10)
    //     [................] [...........]
    //            ^             ^
    //           mid=7         pos=1
    //
    //  move the `low` pointer to the "middle" position, do next iteration.
    if (num < (m+n)/2){
        lowA = mid + 1;
        lowB = pos; 
        if ( highA - lowA > highB - lowB ) {
            return findMedianSortedArrayHelper(A, m, B, n, lowA, highA, lowB, highB);
        }
        return findMedianSortedArrayHelper(B, n, A, m, lowB, highB, lowA, highA);
    }
    // if A[mid] is in the right middle place of the whole two arrays
    if (num > (m+n)/2) {
        highA = mid - 1;
        highB = pos-1;
        if ( highA - lowA > highB - lowB ) {
            return findMedianSortedArrayHelper(A, m, B, n, lowA, highA, lowB, highB);
        }
        return findMedianSortedArrayHelper(B, n, A, m, lowB, highB, lowA, highA);
    }
}
double findMedianSortedArrays(int A[], int m, int B[], int n) {
    //checking the edge cases
    if ( m==0 && n==0 ) return 0.0;
    //if the length of array is odd, return the middle one
    //if the length of array is even, return the average of the middle two numbers
    if ( m==0 ) return n%2==1 ? B[n/2] : (B[n/2-1] + B[n/2])/2.0;
    if ( n==0 ) return m%2==1 ? A[m/2] : (A[m/2-1] + A[m/2])/2.0;
    
    
    //let the longer array be A, and the shoter array be B
    if ( m > n ){
        return findMedianSortedArrayHelper(A, m, B, n, 0, m-1, 0, n-1);
    }
        
    return findMedianSortedArrayHelper(B, n, A, m, 0, n-1, 0, m-1);
}
int main()
{
    int r1[] = {1};
    int r2[] = {2};
 
    int n1 = sizeof(r1)/sizeof(r1[0]);
    int n2 = sizeof(r2)/sizeof(r2[0]);
    printf("Median is 1.5 = %f
", findMedianSortedArrays(r1, n1, r2, n2));
    int ar1[] = {1, 12, 15, 26, 38};
    int ar2[] = {2, 13, 17, 30, 45, 50};
 
    n1 = sizeof(ar1)/sizeof(ar1[0]);
    n2 = sizeof(ar2)/sizeof(ar2[0]);
    printf("Median is 17 = %f
", findMedianSortedArrays(ar1, n1, ar2, n2));
    int ar11[] = {1, 12, 15, 26, 38};
    int ar21[] = {2, 13, 17, 30, 45 };
 
    n1 = sizeof(ar11)/sizeof(ar11[0]);
    n2 = sizeof(ar21)/sizeof(ar21[0]);
    printf("Median is 16 = %f
", findMedianSortedArrays(ar11, n1, ar21, n2));
    int a1[] = {1, 2, 5, 6, 8 };
    int a2[] = {13, 17, 30, 45, 50};
 
    n1 = sizeof(a1)/sizeof(a1[0]);
    n2 = sizeof(a2)/sizeof(a2[0]);
    printf("Median is 10.5 = %f
", findMedianSortedArrays(a1, n1, a2, n2));
    int a10[] = {1, 2, 5, 6, 8, 9, 10 };
    int a20[] = {13, 17, 30, 45, 50};
 
    n1 = sizeof(a10)/sizeof(a10[0]);
    n2 = sizeof(a20)/sizeof(a20[0]);
    printf("Median is 9.5 = %f
", findMedianSortedArrays(a10, n1, a20, n2));
    int a11[] = {1, 2, 5, 6, 8, 9 };
    int a21[] = {13, 17, 30, 45, 50};
 
    n1 = sizeof(a11)/sizeof(a11[0]);
    n2 = sizeof(a21)/sizeof(a21[0]);
    printf("Median is 9 = %f
", findMedianSortedArrays(a11, n1, a21, n2));
    int a12[] = {1, 2, 5, 6, 8 };
    int a22[] = {11, 13, 17, 30, 45, 50};
 
    n1 = sizeof(a12)/sizeof(a12[0]);
    n2 = sizeof(a22)/sizeof(a22[0]);
    printf("Median is 11 = %f
", findMedianSortedArrays(a12, n1, a22, n2));
    int b1[] = {1 };
    int b2[] = {2,3,4};
 
    n1 = sizeof(b1)/sizeof(b1[0]);
    n2 = sizeof(b2)/sizeof(b2[0]);
    printf("Median is 2.5 = %f
", findMedianSortedArrays(b1, n1, b2, n2));
    return 0;
}

     5. C 語言

#include <stdio.h>
#include <stdlib.h>

static double find_kth(int a[], int alen, int b[], int blen, int k)  
{  
    /* Always assume that alen is equal or smaller than blen */ 
    if (alen > blen) {
        return find_kth(b, blen, a, alen, k);
    }

    if (alen == 0) {
        return b[k - 1];
    }

    if (k == 1) {
        return a[0] < b[0] ? a[0] : b[0];
    }

    /* Divide k into two parts */
    int ia = k / 2 < alen ? k / 2 : alen;
    int ib = k - ia;  
    if (a[ia - 1] < b[ib - 1]) {
        /* a[ia - 1] must be ahead of k-th */
        return find_kth(a + ia, alen - ia, b, blen, k - ia);
    } else if (a[ia - 1] > b[ib - 1]) {  
        /* b[ib - 1] must be ahead of k-th */
        return find_kth(a, alen, b + ib, blen - ib, k - ib);
    } else {
        return a[ia - 1];
    }
}

static double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size)
{
    int half = (nums1Size + nums2Size) / 2;
    if ((nums1Size + nums2Size) & 0x1) {
        return find_kth(nums1, nums1Size, nums2, nums2Size, half + 1);
    } else {
        return (find_kth(nums1, nums1Size, nums2, nums2Size, half) + find_kth(nums1, nums1Size, nums2, nums2Size, half + 1)) / 2;
    }
}

int main(int argc, char **argv)
{
    int r1[] = {1};
    int r2[] = {2};
 
    int n1 = sizeof(r1)/sizeof(r1[0]);
    int n2 = sizeof(r2)/sizeof(r2[0]);

    printf("Median is 1.5 = %f
", findMedianSortedArrays(r1, n1, r2, n2));

    int ar1[] = {1, 12, 15, 26, 38};
    int ar2[] = {2, 13, 17, 30, 45, 50};
 
    n1 = sizeof(ar1)/sizeof(ar1[0]);
    n2 = sizeof(ar2)/sizeof(ar2[0]);

    printf("Median is 17 = %f
", findMedianSortedArrays(ar1, n1, ar2, n2));

    int ar11[] = {1, 12, 15, 26, 38};
    int ar21[] = {2, 13, 17, 30, 45 };
 
    n1 = sizeof(ar11)/sizeof(ar11[0]);
    n2 = sizeof(ar21)/sizeof(ar21[0]);

    printf("Median is 16 = %f
", findMedianSortedArrays(ar11, n1, ar21, n2));

    int a1[] = {1, 2, 5, 6, 8 };
    int a2[] = {13, 17, 30, 45, 50};
 
    n1 = sizeof(a1)/sizeof(a1[0]);
    n2 = sizeof(a2)/sizeof(a2[0]);

    printf("Median is 10.5 = %f
", findMedianSortedArrays(a1, n1, a2, n2));

    int a10[] = {1, 2, 5, 6, 8, 9, 10 };
    int a20[] = {13, 17, 30, 45, 50};
 
    n1 = sizeof(a10)/sizeof(a10[0]);
    n2 = sizeof(a20)/sizeof(a20[0]);

    printf("Median is 9.5 = %f
", findMedianSortedArrays(a10, n1, a20, n2));

    int a11[] = {1, 2, 5, 6, 8, 9 };
    int a21[] = {13, 17, 30, 45, 50};
 
    n1 = sizeof(a11)/sizeof(a11[0]);
    n2 = sizeof(a21)/sizeof(a21[0]);

    printf("Median is 9 = %f
", findMedianSortedArrays(a11, n1, a21, n2));

    int a12[] = {1, 2, 5, 6, 8 };
    int a22[] = {11, 13, 17, 30, 45, 50};
    return 0;
}

看完上述內容，你們對如何找出兩個排序數組的中位數有進一步的了解嗎？如果還想了解更多知識或者相關內容，請關注億速云行業資訊頻道，感謝大家的支持。