题目
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000
提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
思路
中位数：对于偶数长度来说寻找中间的两个数据的平均值，对于奇数长度来说寻找中间的那个数据
对有序的两个数组寻找中间的数据，我们可以使用双指针类似与合并两个有序数组，时间复杂度O（m+n）
优化：因为我们是在排序的数组中寻找目标值，所以我们可以使用二分法，去掉没有意义的遍历
对于长度分别为m、n的数组，m+n为偶数：k = (m+n)/2-1、m+n为奇数：k = (m+n)/2、
所以我们是寻找两个数组合并后有序数组的第k个元素。
实现
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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
| private static class Solution {
int length1, length2, totalLength;
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
length1 = nums1.length;
length2 = nums2.length;
totalLength = length1 + length2;
if (totalLength % 2 == 1) {
return getMedian(nums1, nums2, totalLength / 2 + 1);
} else {
return (getMedian(nums1, nums2, totalLength / 2) + getMedian(nums1, nums2, totalLength / 2 + 1)) / 2.0;
}
}
private double getMedian(int[] nums1, int[] nums2, int k) {
int index1 = 0, index2 = 0;
while (true) {
if (index1 == length1) {
return nums2[index2 + k - 1];
}
if (index2 == length2) {
return nums1[index1 + k - 1];
}
if (k == 1) {
return Math.min(nums1[index1], nums2[index2]);
}
int half = k / 2;
int newIndex1 = Math.min(index1 + half, length1) - 1;
int newIndex2 = Math.min(index2 + half, length2) - 1;
int pivot1 = nums1[newIndex1], pivot2 = nums2[newIndex2];
if (pivot1 <= pivot2) {
k -= (newIndex1 - index1 + 1);
index1 = newIndex1 + 1;
} else {
k -= (newIndex2 - index2 + 1);
index2 = newIndex2 + 1;
}
}
}
}
|
