题目描述
给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。
请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
你可以假设 nums1 和 nums2 不会同时为空。
示例 1:
1
2
3
4
| nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0
|
示例 2:
1
2
3
4
| nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 /2 = 2.5
|
思路
中位数是指将数据按大小顺序排列起来，形成一个数列，居于数列中间位置的那个数据。中位数用Me表示。
题目中给定的是两个有序数组，可以将两个数组重新排序组合成一个新的有序数组，这样中位数就可以很方便求出来了。
代码
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
| public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int l1 = nums1.length;
int l2 = nums2.length;
int length = l1 + l2;
int[] nums = new int[length];
for (int i = 0, a = 0, b = 0; i < length; i++) {
if (a == l1) {
nums[i] = nums2[b];
b++;
continue;
}
if (b == l2) {
nums[i] = nums1[a];
a++;
continue;
}
if (nums1[a] <= nums2[b]) {
nums[i] = nums1[a];
a++;
} else {
nums[i] = nums2[b];
b++;
}
}
return length % 2 != 0 ? nums[length / 2] : ((nums[length / 2 - 1] + nums[length / 2])) / 2.0;
}
|