Given two sorted arrays nums1
and nums2
of size m
and n
respectively, return the median of the two sorted arrays.
The overall run time complexity should be O(log (m+n))
.
Example 1:
Input: nums1 = [1,3], nums2 = [2] Output: 2.00000 Explanation: merged array = [1,2,3] and median is 2.
Example 2:
Input: nums1 = [1,2], nums2 = [3,4] Output: 2.50000 Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
public static double findMedian(int[] A, int[] B) {标签:lenB,lenA,return,beginB,Arrays,ma,Median,int,Sorted From: https://www.cnblogs.com/MarkLeeBYR/p/16843869.html
int lenA = A.length;
int lenB = B.length;
int totalLen = lenA + lenB;
if (totalLen % 2 == 1)
return helper(A, 0, lenA, B, 0, lenB, totalLen / 2 + 1);
else {
int var1 = helper(A, 0, lenA, B, 0, lenB, totalLen / 2);
int var2 = helper(A, 0, lenA, B, 0, lenB, totalLen / 2 + 1);
return (double)(var1 + var2) / 2;
}
}
private static int helper(int[] A, int beginA, int lenA, int[] B, int beginB, int lenB, int k) {
if (lenA > lenB)
return helper(B, beginB, lenB, A, beginA, lenA, k);
if (lenA == 0)
return B[beginB + k - 1];
if (k == 1)
return Math.min(A[beginA], B[beginB]);
int ma = Math.min(lenA, k / 2);//把k分成两部分
int mb = k - ma;
if (A[beginA + ma - 1] < B[beginB + mb - 1])
return helper(A, beginA + ma, lenA - ma, B, beginB, lenB, k - ma);//把A数组前面ma个元素去掉
else if (A[beginA + ma - 1] > B[beginB + mb - 1])
return helper(A, beginA, lenA, B, beginB + mb, lenB - mb, k - mb);//把B数组前面mb个元素去掉
else
return A[beginA + ma - 1];
}