4 Median of Two Sorted Arrays

1. Question

There are two sorted arrays nums1and 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:
1
nums1 = [1, 3]
2
nums2 = [2]
3
4
The median is 2.0
Copied!
Example 2:
1
nums1 = [1, 2]
2
nums2 = [3, 4]
3
4
The median is (2 + 3)/2 = 2.5
Copied!

2. Implementation

(1) Binary Search
思路: 这题要我们求两个有序数组的合并后的中位数,其实就相当于找第k个数,其中k = (m + n)/2, m和n分别为两个数组的长度。我们可以利用二分的思想,缩小搜索的范围。做法是,分别对两个数组nums1和nums2找出各自前k/2个数,假设nums1的第k/2个数的位置是m, nums2的第k/2个数的位置是n, 如果nums1[m] < nums2[n], 说明nums1的前m个数肯定小于第k个数,所以抛弃num1的前k/2个数。这里用反证法证明. 最后要注意一些边界条件处理
1
class Solution {
2
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
3
int len = nums1.length + nums2.length;
4
5
if (len % 2 == 0) {
6
return 0.5 * findKthNumber(nums1, 0, nums2, 0, len/2 + 1) + 0.5 * findKthNumber(nums1, 0, nums2, 0, len/2);
7
}
8
else {
9
return findKthNumber(nums1, 0, nums2, 0, len/2 + 1);
10
}
11
}
12
13
public int findKthNumber(int[] nums1, int index1, int[] nums2, int index2, int k) {
14
if (index1 >= nums1.length) {
15
return nums2[index2 + k - 1];
16
}
17
18
if (index2 >= nums2.length) {
19
return nums1[index1 + k - 1];
20
}
21
22
if (k == 1) {
23
return Math.min(nums1[index1], nums2[index2]);
24
}
25
26
// 减一是因为k指的是k个元素,而数组是从0开始
27
int mid = k/2 - 1;
28
29
int mid1 = index1 + mid >= nums1.length ? Integer.MAX_VALUE : nums1[index1 + mid];
30
int mid2 = index2 + mid >= nums2.length ? Integer.MAX_VALUE : nums2[index2 + mid];
31
32
if (mid1 < mid2) {
33
return findKthNumber(nums1, index1 + k/2, nums2, index2, k - k/2);
34
}
35
else {
36
return findKthNumber(nums1, index1, nums2, index2 + k/2, k - k/2);
37
}
38
}
39
}
Copied!

3. Time & Space Complexity

Binary Search: 时间复杂度O(log(m + n)), 空间复杂度O(log(m + n)),因为递归