如何找出两个排序数组的中位数
发表于：2024-10-17 作者：千家信息网编辑
千家信息网最后更新 2024年10月17日，今天就跟大家聊聊有关如何找出两个排序数组的中位数，可能很多人都不太了解，为了让大家更加了解，小编给大家总结了以下内容，希望大家根据这篇文章可以有所收获。一、说明给定两个大小为 m 和 n 的有序数组
千家信息网最后更新 2024年10月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安全错误
数据库的锁怎样保障安全
在线词典数据库设计
数据库python与sql
学校的管理 数据库
计算机软件开发技能有哪些
杭州西奥扶梯服务器查故障
东莞美送网络技术有限公司
软件开发一般做什么项目
中南大学数据库答案
数据库工程师学习路线
国家工控网络安全
中联服务器管理工具登录
网络技术专业能考哪些证
网络安全文明上网的4不
初期软件开发做什么
为什么就是连不上服务器
用友数据库表结构
泰拉瑞一直显示正在启动服务器
服务器端的编程语言
邯郸工控软件开发哪家正规
八度网络服务器托管
万有力网络技术怎么样
2b2t服务器版本是什么
四川服务器硬盘多少钱
苏州打造智慧工地软件开发
大型软件开发需要设备
一个数据库只能有一个关系表
星球大战陨落的骑士团数据库
北京华翼互联网络科技有限公司
学校网络安全法宣传报道
城步县网络安全检测
