题干
来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/median-of-two-sorted-arrays/
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 $ O(\log (m+n))$。
1
2
3
4
5
6
7
8
9
10
11
| 示例 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
|
1
2
3
4
5
6
7
8
9
| 提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106
|
思路
中位数将整个合起来的数组分为两个部分，如果是偶数个，那么中间两个数的平均值；如果是奇数个，那么是中间一个数字。
因此可以进行二分搜索，怎么搜成了关键问题：一种思路是直接搜索中位数的值，然后判断符不符合，但是好像不满足题干要求；另一种是搜索数组内的中位数，构造很困难。
官方思路学习: https://leetcode.cn/problems/median-of-two-sorted-arrays/solution/xun-zhao-liang-ge-you-xu-shu-zu-de-zhong-wei-s-114/
AC 代码
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
45
| class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if(nums1.size() > nums2.size()){
return findMedianSortedArrays(nums2,nums1);
}
int m = nums1.size();
int n = nums2.size();
int mid1,mid2;
double ans = 0;
int left = 0;
int right = m;
int i = 0, j = 0;
int nums1_i_1 = 0, nums1_i = 0, nums2_j_1 = 0, nums2_j = 0;
while(left <= right){
i = (left + right) / 2;
j = ( m + n + 1) / 2 - i;
nums1_i_1 = (i==0?INT_MIN:nums1[i-1]);
nums1_i = (i==m?INT_MAX:nums1[i]);
nums2_j_1 = (j==0?INT_MIN:nums2[j-1]);
nums2_j = (j==n?INT_MAX:nums2[j]);
if(nums1_i_1 <= nums2_j){
mid1 = max(nums1_i_1, nums2_j_1);
mid2 = min(nums1_i, nums2_j);
left = i + 1;
}else{
right = i - 1;
}
}
if(( m + n ) % 2 == 0){
ans = (mid1 + mid2) / 2.0;
}else{
ans = mid1;
}
return ans;
}
};
|