0004. Median of Two Sorted Arrays
Description
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
1
2
3
4
2
3
4
示例 2:
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5
1
2
3
4
2
3
4
(en)https://leetcode.com/problems/median-of-two-sorted-arrays/
(中文)https://leetcode-cn.com/problems/median-of-two-sorted-arrays/
Solutions
Solution1
由于在做题时，实在没有想到什么高效的解法，因此，直接使用归并排序 (MergeSort) 中归并的想法。将两个已排序数组归并起来，然后再取中间值。
注意
此解法并不满足题目要求时间复杂度需求
/*
Complexity Analysis:
Time complexity: O(m +n )
Space complexity: O(m + n)
*/
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
// using the idea of mergeSort
int m = nums1.length;
int n = nums2.length;
int[] merged = new int[m + n];
int left = 0, right = 0;
for (int i = 0; i < merged.length; i++) {
if (left >= m) // no elements left in nums1
merged[i] = nums2[right++];
else if (right >= n) // no elements left in nums2
merged[i] = nums1[left++];
else if (nums1[left] < nums2[right])
merged[i] = nums1[left++];
else
merged[i] = nums2[right++];
}
// if only one element in the merged array.
if (merged.length == 1)
return merged[0];
int mid = merged.length / 2;
return merged.length % 2 == 0 ? (double)(merged[mid]+merged[mid-1]) /2: (double)(merged[mid]);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
Submission status
果然，提交完之后，发现击败 % 的人而已，运行时间 32 ms。显然，这种做法并不是理想的解法。