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
给定两个有序数组nums1和nums2大小分别为m和n。
找到这两个数组的中位数。整体运行时间复杂度应为O(log(m + n))。
归并排序,二路归并,归并到一半就出结果了。注意结果是小数。
注意测试数据:
num1 = [],num2 = [1,2,3]
num1 = [1,2,3],num2 = [1]
num1 = [1],num2 = [1,2,3]
public class MedianTwoArrays {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int T = nums1.length + nums2.length;
double result;
List<Integer> nums3 = new ArrayList<>(T);
int i1 = 0;
int i2 = 0;
int i3 = 0;
int num1;
int num2;
while (i3 <= T / 2) {
num1 = (i1 == nums1.length) ? Integer.MAX_VALUE : nums1[i1];
num2 = (i2 == nums2.length) ? Integer.MAX_VALUE : nums2[i2];
if (num1 < num2) {
nums3.add(num1);
i1++;
} else {
nums3.add(num2);
i2++;
}
i3++;
}
int temp;
if (T % 2 != 0) {
temp = nums3.get(i3 - 1);
result = (temp + temp) / 2.0;
} else {
temp = nums3.get(i3 - 2) + nums3.get(i3 - 1);
result = temp / 2.0;
}
return result;
}
}