There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
Solution：
https://leetcode.com/problems/median-of-two-sorted-arrays/solution/
中位数的意义：
中位数左边的所有数都小于中位数右边的所有数：
设有两个数组A，B,大小分别为m，n（m<=n），两个数组的中位数为第k个数，
找到两条分割AB的线
A的分割线i（0-m）
B的分割线j（k-i）
i实际起始点：k/2-1；终止点：m
比较的是A（i-1）B（j）和B（j-1）和A（i），
如果A（i-1）< B（j）
i太小，i需要增加，j随着减小。
k 减小两个数，类似于掐头去尾，再寻找中间的数。i前进一个数字。
注意：⚠️还要考虑A（i-1）或者B（i-1）不存在的情况
https://leetcode.com/problems/median-of-two-sorted-arrays/solution/
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;
}
}
网友评论