给定两个大小为 m 和 n 的有序数组 nums1
和 nums2
。
请你找出这两个有序数组的中位数,并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1
和 nums2
不会同时为空。
示例 1:
1 2 3 4
|
nums1 = [1, 3] nums2 = [2]
则中位数是 2.0
|
示例 2:
1 2 3 4
|
nums1 = [1, 2] nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
|
2. 题解
2.1. 思路
2.2. 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 35 36 37 38 39 40 41 42 43 44
|
class { public double findMedianSortedArrays(int[] A, int[] B) { int m = A.length; int n = B.length; if (m > n) { return findMedianSortedArrays(B, A); }
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 = i + 1; } else if (i > iMin && A[i - 1] > B[j]) { 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 ((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; } }
|
近期评论