如何找出两个排序数组的中位数
发表于：2025-11-07 作者：千家信息网编辑
千家信息网最后更新 2025年11月07日，今天就跟大家聊聊有关如何找出两个排序数组的中位数，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。一、说明给定两个大小为 m 和 n 的有序数组
千家信息网最后更新 2025年11月07日如何找出两个排序数组的中位数
今天就跟大家聊聊有关如何找出两个排序数组的中位数，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。
一、说明
给定两个大小为 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;}
看完上述内容，你们对如何找出两个排序数组的中位数有进一步的了解吗？如果还想了解更多知识或者相关内容，请关注行业资讯频道，感谢大家的支持。
中位数
语言
两个
数组
内容
方式
排序
有序
示例
复杂
复杂度
大小
方案
时间
更多
知识
算法
篇文章
行业
解决方案
数据库的安全要保护哪些东西
数据库安全各自的含义是什么
生产安全数据库录入
数据库的安全性及管理
数据库安全策略包含哪些
海淀数据库安全审计系统
建立农村房屋安全信息数据库
易用的数据库客户端支持安全管理
连接数据库失败ssl安全错误
数据库的锁怎样保障安全
服务器处理器看什么参数
金仓数据库资源文件
数据库开发小型选课系统
小蜜脚本链接服务器失败
华南理工大学网络安全考研
公安内网网络安全培训课件
数据库dll什么意思
数据库表中属性列的 删除
svn服务器租用
人大网络安全应急预案
最流行的数据库属于
城市网络安全指挥中心
边缘应用服务器
第25条规定的网络安全意识
小天网络技术QQ音乐
天津软件开发岗待遇
美国网站服务器
自己搭建私人dns服务器犯法吗
济南有实力的浪潮服务器供应商
突然断电导致数据库停止
数据库的大表和小表标准
it软件开发薪酬
戴尔服务器开机后黑屏
外包软件开发利润率
无限法则登录服务器进不去
空间数据库怎么合并
表空间是不是数据库
广州广睿知产网络技术有限
沧州导航软件开发
湖南企业党建软件开发系统
