#P4079. 寻找两个正序数组的中位数
-
ID: 2320
Tried: 35
Accepted: 11
Difficulty: 6
寻找两个正序数组的中位数
题目内容
给定两个大小分别为 m和 n的正序（从小到大）数组 nums1和 nums2。请你找出并返回这两个正序数组的中位数。
算法的时间复杂度应该为 O(log (m+n))。
输入描述
- 第一行输入一个整数 m，表示数组 nums1 的长度。
- 第二行输入 m 个整数，表示数组 nums1。
- 第三行输入一个整数 n，表示数组 nums2 的长度。
- 第四行输入 n 个整数，表示数组 nums2。
输出描述
输出一个浮点数，表示两个数组的 中位数，精确到 5 位小数。
样例1
输入
2
1 3
1
2
输出
2.00000
说明
合并数组 = [1,2,3] ，中位数 2
样例2
输入
2
1 2
2
3 4
输出
2.50000
说明
合并数组= [1,2,3,4] ，中位数 (2+3)/2=2.5
提示：
- nums1.length==m
- nums2.length==n
- 0<=m<=1000
- 0<=n<=1000
- 1<=m+n<=2000
- −106<=nums1[i],nums2[i]<=106
寻找两个正序数组的中位数
题解思路
方法：二分查找（O(log(m+n))）
我们不需要真的合并 nums1 和 nums2，而是通过 二分查找 在 较短的数组上 进行分割，确定中位数。
1. 目标
我们要找到 合并后数组的中位数：
- 若总长度是奇数，中位数是第
(m+n)//2 + 1个元素。 - 若总长度是偶数，中位数是 第
(m+n)//2和(m+n)//2 + 1个元素的平均值。
2. 二分查找的分割策略
我们 始终在较短的数组 nums1 上二分（保证 m <= n），选择一个分割点 i，使得：
nums1[0:i] 和 nums2[0:j] 在合并后构成中位数的左半部分
nums1[i:m] 和 nums2[j:n] 在合并后构成中位数的右半部分
其中 j = (m + n + 1) / 2 - i 确保左侧部分的长度接近于右侧部分。
3. 二分调整
- 若
nums1[i] < nums2[j-1]，说明nums1的分割太靠左，需要i右移。 - 若
nums1[i-1] > nums2[j]，说明nums1的分割太靠右，需要i左移。
最终，找到合适的 i 和 j 后，就可以计算 中位数。
代码实现
Python 代码
import sys
def findMedianSortedArrays(nums1, nums2):
if len(nums1) > len(nums2): # 确保 nums1 是较短的数组
nums1, nums2 = nums2, nums1
m, n = len(nums1), len(nums2)
left, right = 0, m
half_len = (m + n + 1) // 2
while left <= right:
i = (left + right) // 2
j = half_len - i # 确保左侧部分长度接近右侧部分
if i < m and nums1[i] < nums2[j - 1]: # i 太小，右移
left = i + 1
elif i > 0 and nums1[i - 1] > nums2[j]: # i 太大，左移
right = i - 1
else: # 找到了合适的 i
max_of_left = max(nums1[i - 1] if i > 0 else float('-inf'),
nums2[j - 1] if j > 0 else float('-inf'))
if (m + n) % 2 == 1:
return round(max_of_left, 5) # 奇数长度，直接返回
min_of_right = min(nums1[i] if i < m else float('inf'),
nums2[j] if j < n else float('inf'))
return round((max_of_left + min_of_right) / 2, 5) # 偶数长度，返回平均值
# 读取输入
m = int(sys.stdin.readline().strip())
nums1 = list(map(int, sys.stdin.readline().split())) if m > 0 else []
n = int(sys.stdin.readline().strip())
nums2 = list(map(int, sys.stdin.readline().split())) if n > 0 else []
# 输出结果
median = findMedianSortedArrays(nums1, nums2)
print(f"{median:.5f}")
Java 代码
import java.util.Scanner;
public class Main {
public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
if (nums1.length > nums2.length) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.length, n = nums2.length;
int left = 0, right = m, halfLen = (m + n + 1) / 2;
while (left <= right) {
int i = (left + right) / 2;
int j = halfLen - i;
if (i < m && nums1[i] < nums2[j - 1]) {
left = i + 1;
} else if (i > 0 && nums1[i - 1] > nums2[j]) {
right = i - 1;
} else {
int maxOfLeft = Math.max(i > 0 ? nums1[i - 1] : Integer.MIN_VALUE,
j > 0 ? nums2[j - 1] : Integer.MIN_VALUE);
if ((m + n) % 2 == 1) {
return maxOfLeft;
}
int minOfRight = Math.min(i < m ? nums1[i] : Integer.MAX_VALUE,
j < n ? nums2[j] : Integer.MAX_VALUE);
return (maxOfLeft + minOfRight) / 2.0;
}
}
return 0.0;
}
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int m = scanner.nextInt();
int[] nums1 = new int[m];
for (int i = 0; i < m; i++) nums1[i] = scanner.nextInt();
int n = scanner.nextInt();
int[] nums2 = new int[n];
for (int i = 0; i < n; i++) nums2[i] = scanner.nextInt();
System.out.printf("%.5f\n", findMedianSortedArrays(nums1, nums2));
}
}
c++代码
#include <bits/stdc++.h>
using namespace std;
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
if (nums1.size() > nums2.size()) {
return findMedianSortedArrays(nums2, nums1); // 确保 nums1 是较短的数组
}
int m = nums1.size(), n = nums2.size();
int left = 0, right = m, half_len = (m + n + 1) / 2;
while (left <= right) {
int i = (left + right) / 2;
int j = half_len - i;
if (i < m && nums1[i] < nums2[j - 1]) {
left = i + 1; // i 太小，右移
} else if (i > 0 && nums1[i - 1] > nums2[j]) {
right = i - 1; // i 太大，左移
} else {
// 找到合适的 i
int max_of_left = max(i > 0 ? nums1[i - 1] : INT_MIN,
j > 0 ? nums2[j - 1] : INT_MIN);
if ((m + n) % 2 == 1) {
return max_of_left; // 奇数长度，返回中位数
}
int min_of_right = min(i < m ? nums1[i] : INT_MAX,
j < n ? nums2[j] : INT_MAX);
return (max_of_left + min_of_right) / 2.0; // 偶数长度，返回均值
}
}
return 0.0; // 兜底逻辑，实际不会执行到这里
}
int main() {
int m, n;
cin >> m;
vector<int> nums1(m);
for (int i = 0; i < m; i++) {
cin >> nums1[i];
}
cin >> n;
vector<int> nums2(n);
for (int i = 0; i < n; i++) {
cin >> nums2[i];
}
cout << fixed << setprecision(5) << findMedianSortedArrays(nums1, nums2) << endl;
return 0;
}