如何找出两个排序数组的中位数
发表于：2025-01-17 作者：千家信息网编辑
千家信息网最后更新 2025年01月17日，今天就跟大家聊聊有关如何找出两个排序数组的中位数，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。一、说明给定两个大小为 m 和 n 的有序数组
千家信息网最后更新 2025年01月17日如何找出两个排序数组的中位数
今天就跟大家聊聊有关如何找出两个排序数组的中位数，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。
一、说明
给定两个大小为 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安全错误
数据库的锁怎样保障安全
轻数据库
yii2 数据库操作
三种数据库格式化时间
达蒙数据库调优视频
服务器跟机架靠什么固定
服务器清理
网络安全产品供求
服务器管理的工作
湖南测控labview软件开发
可以同时备份一个或多个数据库
山东有网络安全专业的大学
数据港网络安全
商丘学院计算机网络技术
手机卡顿无法连接到服务器
软件开发接口定义规范
浙江台州制造业erp软件开发
铜仁oa办公软件开发费用
河北前端软件开发靠谱吗
安徽科技学院互联网
政务系统软件开发
南通海航软件开发诚信服务
德勤软件开发待遇咋样
班会网络安全为人民
无锡互联网软件开发费用是多少
政府网络安全保卫部职责
金蝶服务器ip咋样让他固定
巨灾风险管理数据库作用
一年级网络安全教育教学教案
网络安全技能竞赛题目国赛
网络安全目标英文
