4. Median of Two Sorted Arrays
4. Median of Two Sorted Arrays
- 刷题仓库地址
- 4. Median of Two Sorted Arrays
- 10. Regular Expression Matching
- 23. Merge k Sorted Lists
- 25. Reverse Nodes in k-Group
- 30. Substring with Concatenation of All Words
- 32. Longest Valid Parentheses
Description
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
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
Translation
给定两个有序数组nums1和nums2大小分别为m和n。
找到这两个数组的中位数。整体运行时间复杂度应为O(log(m + n))。
Ideas
归并排序,二路归并,归并到一半就出结果了。注意结果是小数。
Note
注意测试数据:
num1 = [],num2 = [1,2,3]
num1 = [1,2,3],num2 = [1]
num1 = [1],num2 = [1,2,3]
Accept Code
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;
}
}
转载请注明出处
本文链接:http://zdran.com/20180327.html