class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int size = nums1.length + nums2.length;
int msize = size / 2;
int i = 0;
int j = 0;
double median = nums1[0];
double firstm = 0.0;
double secm = 0.0;
if (msize % 2 == 0) {
while (i + j < msize) {
if (nums1[i] < nums2[j]) {
firstm = nums1[i];
i++;
} else {
firstm = nums2[j];
j++;
}
}
secm = (nums1[i] < nums2[j] ? nums1[i] : nums2[j]);
median = (firstm + secm) / 2;
} else {
while (i + j < msize) {
if (nums1[i] < nums2[j]) {
firstm = nums1[i];
i++;
} else {
firstm = nums2[j];
j++;
}
}
median = firstm;
}
return median;
}
}
흑흑
public class Solution {
public double findMedianSortedArrays(int[] A, int[] B) {
int m = A.length, n = B.length;
int l = (m + n + 1) / 2;
int r = (m + n + 2) / 2;
return (getkth(A, 0, B, 0, l) + getkth(A, 0, B, 0, r)) / 2.0;
}
public double getkth(int[] A, int aStart, int[] B, int bStart, int k) {
if (aStart > A.length - 1) return B[bStart + k - 1];
if (bStart > B.length - 1) return A[aStart + k - 1];
if (k == 1) return Math.min(A[aStart], B[bStart]);
int aMid = Integer.MAX_VALUE, bMid = Integer.MAX_VALUE;
if (aStart + k/2 - 1 < A.length) aMid = A[aStart + k/2 - 1];
if (bStart + k/2 - 1 < B.length) bMid = B[bStart + k/2 - 1];
if (aMid < bMid)
return getkth(A, aStart + k/2, B, bStart, k - k/2);// Check: aRight + bLeft
else
return getkth(A, aStart, B, bStart + k/2, k - k/2);// Check: bRight + aLeft
}
}
Runtime: 3 ms, faster than 45.74% of Java online submissions for Median of Two Sorted Arrays.
Memory Usage: 46.9 MB, less than 6.20% of Java online submissions for Median of Two Sorted Arrays.