如何找出两个排序数组的中位数

今天就跟大家聊聊有关如何找出两个排序数组的中位数，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。

一、说明

给定两个大小为 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..
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 // 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 solutiondouble 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 #include 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;}
看完上述内容，你们对如何找出两个排序数组的中位数有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注行业资讯频道，感谢大家的支持。