【算法】4. 寻找两个正序数组的中位数（多语言实现）
【摘要】 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
4. 寻找两个正序数组的中位数：
给定两个大小分别为 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
提示：
- nums1.length == m
- nums2.length == n
- 0 <= m <= 1000
- 0 <= n <= 1000
- 1 <= m + n <= 2000
- -106 <= nums1[i], nums2[i] <= 106
分析
- 面对这道算法题目，二当家的陷入了沉思。
- 这道题第一感觉是合并两个数组再排序，然后直接取中位数，代码量很少，然而很明显时间复杂度和空间复杂度都上去了，相当于把两个有序数组当作无序数组使用了。对于有序这个性质怎么用，官方题解已经很给力了，我无需再赘述，参考了官方和网友的题解。
- 我只用一句话概述一下我从官方题解理解的精髓，将两个有序数组合并后成一个有序数组，数组1中各个元素顺序位置不会变，数组2也一样。所以新数组的前半部分一定是数组1前面连续的一部分（可能是空）和数组2前面连续的一部分组成的，后半部分同理。所以其实只需要知道数组1在新数组前后两部分的切分位置，数组2同理。
题解：
rust
impl Solution {
pub fn find_median_sorted_arrays(nums1: Vec<i32>, nums2: Vec<i32>) -> f64 {
let (n1, n2) = (nums1.len(), nums2.len());
if n1 > n2 {
return Solution::find_median_sorted_arrays(nums2, nums1);
}
let (mut left, mut right) = (0, n1);
// 中位数位置之和
let mid_idx_sum = (n1 + n2 + 1) >> 1;
while left < right {
// 前一部分包含 nums1[0 .. idx1-1] 和 nums2[0 .. idx2-1]
// 后一部分包含 nums1[idx1 .. n1-1] 和 nums2[idx2 .. n2-1]
let idx1 = (left + right + 1) >> 1;
let idx2 = mid_idx_sum - idx1;
let num1_1 = nums1[idx1 - 1];
let num2_2 = nums2[idx2];
if num1_1 > num2_2 {
right = idx1 - 1;
} else {
left = idx1;
}
}
let (idx1, idx2) = (left, mid_idx_sum - left);
// nums1_1, nums1_2, nums2_1, num2_2 分别表示 nums1[idx1-1], nums1[idx1], nums2[idx2-1], nums2[idx2]
let nums1_1 = match idx1 {
0 => i32::MIN,
_ => nums1[idx1 - 1]
};
let nums1_2 = match idx1 {
i if i == n1 => i32::MAX,
_ => nums1[idx1]
};
let nums2_1 = match idx2 {
0 => i32::MIN,
_ => nums2[idx2 - 1]
};
let nums2_2 = match idx2 {
j if j == n2 => i32::MAX,
_ => nums2[idx2]
};
// median1：前一部分的最大值
let median1 = nums1_1.max(nums2_1);
// median2：后一部分的最小值
let median2 = nums1_2.min(nums2_2);
if (n1 + n2) & 1 == 0 {
// 偶数，有两个中位数
(median1 + median2) as f64 / 2.0
} else {
// 奇数，有一个中位数
median1 as f64
}
}
}
go
func findMedianSortedArrays(nums1 []int, nums2 []int) float64 {
n1, n2 := len(nums1), len(nums2)
if n1 > n2 {
return findMedianSortedArrays(nums2, nums1)
}
left, right := 0, n1
// 中位数位置之和
midIdxSum := (n1 + n2 + 1) >> 1
for left < right {
// 前一部分包含 nums1[0 .. idx1-1] 和 nums2[0 .. idx2-1]
// 后一部分包含 nums1[idx1 .. n1-1] 和 nums2[idx2 .. n2-1]
idx1 := (left + right + 1) >> 1
idx2 := midIdxSum - idx1
nums1N1 := nums1[idx1-1]
nums2N2 := nums2[idx2]
if nums1N1 > nums2N2 {
right = idx1 - 1
} else {
left = idx1
}
}
idx1, idx2 := left, midIdxSum-left
// nums1N1, nums1N2, nums2N1, nums2N2 分别表示 nums1[idx1-1], nums1[idx1], nums2[idx2-1], nums2[idx2]
var nums1N1 int
if idx1 == 0 {
nums1N1 = math.MinInt32
} else {
nums1N1 = nums1[idx1-1]
}
var nums1N2 int
if idx1 == n1 {
nums1N2 = math.MaxInt32
} else {
nums1N2 = nums1[idx1]
}
var nums2N1 int
if idx2 == 0 {
nums2N1 = math.MinInt32
} else {
nums2N1 = nums2[idx2-1]
}
var nums2N2 int
if idx2 == n2 {
nums2N2 = math.MaxInt32
} else {
nums2N2 = nums2[idx2]
}
// median1：前一部分的最大值
var median1 int
if nums1N1 > nums2N1 {
median1 = nums1N1
} else {
median1 = nums2N1
}
// median2：后一部分的最小值
var median2 int
if nums1N2 < nums2N2 {
median2 = nums1N2
} else {
median2 = nums2N2
}
if (n1+n2)&1 == 0 {
// 偶数，有两个中位数
return float64(median1+median2) / 2.0
} else {
// 奇数，有一个中位数
return float64(median1)
}
}
c++
class Solution {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
const int n1 = nums1.size(), n2 = nums2.size();
if (n1 > n2) {
return findMedianSortedArrays(nums2, nums1);
}
int left = 0, right = n1;
// 中位数位置之和
const int midIdxSum = (n1 + n2 + 1) >> 1;
while (left < right) {
// 前一部分包含 nums1[0 .. idx1-1] 和 nums2[0 .. idx2-1]
// 后一部分包含 nums1[idx1 .. n1-1] 和 nums2[idx2 .. n2-1]
const int idx1 = (left + right + 1) >> 1;
const int idx2 = midIdxSum - idx1;
const int nums1N1 = nums1[idx1 - 1];
const int nums2N2 = nums2[idx2];
if (nums1N1 > nums2N2) {
right = idx1 - 1;
} else {
left = idx1;
}
}
const int idx1 = left, idx2 = midIdxSum - left;
// nums1N1, nums1N2, nums2N1, nums2N2 分别表示 nums1[idx1-1], nums1[idx1], nums2[idx2-1], nums2[idx2]
const int nums1N1 = (idx1 == 0 ? INT_MIN : nums1[idx1 - 1]);
const int nums1N2 = (idx1 == n1 ? INT_MAX : nums1[idx1]);
const int nums2N1 = (idx2 == 0 ? INT_MIN : nums2[idx2 - 1]);
const int nums2N2 = (idx2 == n2 ? INT_MAX : nums2[idx2]);
// median1：前一部分的最大值
const int median1 = max(nums1N1, nums2N1);
// median2：后一部分的最小值
const int median2 = min(nums1N2, nums2N2);
// 偶数，有两个中位数
// 奇数，有一个中位数
return ((n1 + n2) & 1) == 0 ? (median1 + median2) / 2.0 : median1;
}
};
c
double findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size){
const int n1 = nums1Size, n2 = nums2Size;
if (n1 > n2) {
return findMedianSortedArrays(nums2, nums2Size, nums1, nums1Size);
}
int left = 0, right = n1;
// 中位数位置之和
const int midIdxSum = (n1 + n2 + 1) >> 1;
while (left < right) {
// 前一部分包含 nums1[0 .. idx1-1] 和 nums2[0 .. idx2-1]
// 后一部分包含 nums1[idx1 .. n1-1] 和 nums2[idx2 .. n2-1]
const int idx1 = (left + right + 1) >> 1;
const int idx2 = midIdxSum - idx1;
const int nums1N1 = nums1[idx1 - 1];
const int nums2N2 = nums2[idx2];
if (nums1N1 > nums2N2) {
right = idx1 - 1;
} else {
left = idx1;
}
}
const int idx1 = left, idx2 = midIdxSum - left;
// nums1N1, nums1N2, nums2N1, nums2N2 分别表示 nums1[idx1-1], nums1[idx1], nums2[idx2-1], nums2[idx2]
const int nums1N1 = (idx1 == 0 ? INT32_MIN : nums1[idx1 - 1]);
const int nums1N2 = (idx1 == n1 ? INT32_MAX : nums1[idx1]);
const int nums2N1 = (idx2 == 0 ? INT32_MIN : nums2[idx2 - 1]);
const int nums2N2 = (idx2 == n2 ? INT32_MAX : nums2[idx2]);
// median1：前一部分的最大值
const int median1 = fmax(nums1N1, nums2N1);
// median2：后一部分的最小值
const int median2 = fmin(nums1N2, nums2N2);
// 偶数，有两个中位数
// 奇数，有一个中位数
return ((n1 + n2) & 1) == 0 ? (median1 + median2) / 2.0 : median1;
}
python
class Solution:
def findMedianSortedArrays(self, nums1: List[int], nums2: List[int]) -> float:
n1, n2 = len(nums1), len(nums2)
if n1 > n2:
return self.findMedianSortedArrays(nums2, nums1)
left, right = 0, n1
# 中位数位置之和
mid_idx_sum = (n1 + n2 + 1) >> 1
while left < right:
# 前一部分包含nums1[0..idx1 - 1]和nums2[0..idx2 - 1]
# 后一部分包含nums1[idx1..n1 - 1]和nums2[idx2..n2 - 1]
idx1 = (left + right + 1) >> 1
idx2 = mid_idx_sum - idx1
nums1_1 = nums1[idx1 - 1]
nums2_2 = nums2[idx2]
if nums1_1 > nums2_2:
right = idx1 - 1
else:
left = idx1
idx1, idx2 = left, mid_idx_sum - left
# nums1_1, nums1_2, nums2_1, nums2_2分别表示nums1[idx1 - 1], nums1[idx1], nums2[idx2 - 1], nums2[idx2]
infinty = 2 ** 32
nums1_1 = (-infinty if idx1 == 0 else nums1[idx1 - 1])
nums1_2 = (infinty if idx1 == n1 else nums1[idx1])
nums2_1 = (-infinty if idx2 == 0 else nums2[idx2 - 1])
nums2_2 = (infinty if idx2 == n2 else nums2[idx2])
# median1：前一部分的最大值
median1 = max(nums1_1, nums2_1)
# median2：后一部分的最小值
median2 = min(nums1_2, nums2_2)
# 偶数，有两个中位数
# 奇数，有一个中位数
return (median1 + median2) / 2 if (n1 + n2) & 1 == 0 else median1
java
class Solution {
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
final int n1 = nums1.length, n2 = nums2.length;
if (n1 > n2) {
return findMedianSortedArrays(nums2, nums1);
}
int left = 0, right = n1;
// 中位数位置之和
final int midIdxSum = (n1 + n2 + 1) >> 1;
while (left < right) {
// 前一部分包含 nums1[0 .. idx1-1] 和 nums2[0 .. idx2-1]
// 后一部分包含 nums1[idx1 .. n1-1] 和 nums2[idx2 .. n2-1]
final int idx1 = (left + right + 1) >> 1;
final int idx2 = midIdxSum - idx1;
final int nums1N1 = nums1[idx1 - 1];
final int nums2N2 = nums2[idx2];
if (nums1N1 > nums2N2) {
right = idx1 - 1;
} else {
left = idx1;
}
}
final int idx1 = left, idx2 = midIdxSum - left;
// nums1N1, nums1N2, nums2N1, nums2N2 分别表示 nums1[idx1-1], nums1[idx1], nums2[idx2-1], nums2[idx2]
final int nums1N1 = (idx1 == 0 ? Integer.MIN_VALUE : nums1[idx1 - 1]);
final int nums1N2 = (idx1 == n1 ? Integer.MAX_VALUE : nums1[idx1]);
final int nums2N1 = (idx2 == 0 ? Integer.MIN_VALUE : nums2[idx2 - 1]);
final int nums2N2 = (idx2 == n2 ? Integer.MAX_VALUE : nums2[idx2]);
// median1：前一部分的最大值
final int median1 = Math.max(nums1N1, nums2N1);
// median2：后一部分的最小值
final int median2 = Math.min(nums1N2, nums2N2);
// 偶数，有两个中位数
// 奇数，有一个中位数
return ((n1 + n2) & 1) == 0 ? (median1 + median2) / 2.0 : median1;
}
}
非常感谢你阅读本文~
放弃不难，但坚持一定很酷~
希望我们大家都能每天进步一点点~
本文由 二当家的白帽子：https://bbs.huaweicloud.com/community/usersnew/id_1628396583336561 博客原创~
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）