• 欢迎光临~

4. Median of Two Sorted Arrays

开发技术 开发技术 2022-10-31 次浏览

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) {
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];
}
程序员灯塔
转载请注明原文链接:4. Median of Two Sorted Arrays
喜欢 (0)