来源:Leetcode第四题寻找两个有序数组的中位数
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
先想到了归并两个数组后在从新的有序数组中找中位数,可是这样的时间复杂度是O(m+n),不符合题目要求。
在查看题解之后知道是要用二分的思想。
简单的说,就是同时对两个数组进行切割,使得数组1左边最大数组2右边最小,数组2左边最大<数组1右边最小,这样就有中位数是从两个数组左边最大的值和右边最小的值中取出来。
原解答链接:[寻找中位数](https://leetcode-cn.com/problems/median-of-two-sorted-arrays/solution/4-xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-shu/)
C++代码如下:
<!--code0--
JAVA
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34
| public double find(int[] A,int[] B){ int len1 = A.length; int len2 = B.length; if(len1 > len2) return find(B,A); int iMin = 0 , iMax = len1, mid = (len1 + len2 + 1) / 2; while (iMin < iMax){ int i = (iMax + iMin) / 2; int j = mid - i; if(i < iMax && A[i] < B[j-1]) iMin = i + 1; else if(i > iMin && B[j] < A[i - 1]) iMax = i - 1; else{ 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((len1 + len2) % 2 == 1) return maxLeft; int minRight = 0; if(i == len1) minRight = B[j]; else if(j == len2) minRight = A[i]; else minRight = Math.min(B[j],A[i]); return (minRight + maxLeft) / 2.0; } } return 00.00; }
|