LeetCode 热题 100_寻找两个正序数组的中位数（68_4_困难_C++）(二分查找)（先合并再挑选中位数；划分数组（二分查找））
LeetCode 热题 100_寻找两个正序数组的中位数（68_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、复杂度分析：
① 时间复杂度：O(m+n)，m和n分别为两个有序数组元素的个数。合并两个有序数组的时间复杂度为O(m+n)。查找合并后的中位数时间为O(1)。
② 空间复杂度：O(m+n)，需要一个额外的数组来存储合并后的数组。
思路二（划分数组（二分查找））：
1、我们首先考虑一个有序数组取中位数的情况：nums=[2,3,4,6,8,9,10,12,18,20] ， n=10。
我们可以将分隔线放在8和9之间：[2,3,4,6,8 | 9 ,10,12,18,20]。(当元素个数为奇数时，左侧元素多1)
将nums拆分成两个数组（分隔线的情况如下）：
nums1=[3,8 | 9,10]
nums2=[2,4,6 | 12,18,20]
将nums拆分成两个数组（分隔线的情况如下）：
nums1=[2,3,4 |]
nums2=[6,8 | 9,10,12,18,20]
发现其中的规律：
① 分隔线的左侧元素值小于右侧元素值，且当前数组右侧的元素值大于另一个数组左侧的元素值。
② 分隔线左侧的元素个数（两个数组）等于分隔线右侧的元素个数或者左侧比右侧多一个元素。
③ 中位数一定在分隔线的左右两侧元素中选取。
2、通过分析出的规律可得出解题的步骤如下：
① 确定 nums1 中的分隔线（二分查找），再通过分隔线左右两侧元素的个数关系，确定 nums2 中的分隔线。
② 确定分隔线后，若nums1中左侧元素 > nums2中的右侧元素，则nums1中的分隔线需左移减小nums1中左侧元素的值（这里和下方的左侧元素和右侧元素指的是分隔线相邻的元素）。
③ 确定分隔线后，若nums2中左侧元素 > nums1中的右侧元素，则nums1中的分隔线需右移，增大nums1中右侧元素的值。
④ 确定分隔线后，若nums1中左侧元素 <= nums2中的右侧元素，且nums2中左侧元素 <= nums1中的右侧元素。若两个数组元素总和为奇数则输出左侧元素的最大值（nums1和nums2分隔线左侧）。若两个数组元素总和为偶数则输出左侧元素的最大值（nums1和nums2分隔线左侧）+右侧元素的最小值 再除以 2。
官方的视频题解链接(挺不错的)
3、复杂度分析
① 时间复杂度：O(logmin(m,n)))，其中 m 和 n 分别是数组 nums1和 nums2 的长度，只对其中较小的数组进行二分查找。
② 空间复杂度：O(1)。
代码实现
代码实现（思路一（先合并再挑选中位数））：
class Solution1 {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
// 初始化指针 i, j 用于遍历 nums1 和 nums2，k 用于遍历合并后的数组 merge
int i = 0, j = 0, k = 0;
// 创建一个合并后的数组 merge，其大小为 nums1 和 nums2 长度之和
vector<int> merge(nums1.size() + nums2.size());
// 合并两个已排序的数组 nums1 和 nums2 到 merge 数组中
while (i < nums1.size() && j < nums2.size()) {
// 比较 nums1 和 nums2 中当前元素的大小，选择较小的元素放入 merge 数组
if (nums1[i] <= nums2[j]) {
merge[k++] = nums1[i++]; // 将 nums1 的当前元素放入 merge 中
} else {
merge[k++] = nums2[j++]; // 将 nums2 的当前元素放入 merge 中
}
}
// 如果 nums1 中还有剩余的元素，继续加入 merge 数组
while (i < nums1.size()) {
merge[k++] = nums1[i++];
}
// 如果 nums2 中还有剩余的元素，继续加入 merge 数组
while (j < nums2.size()) {
merge[k++] = nums2[j++];
}
// 计算合并后数组的中位数索引
int mid = (nums1.size() + nums2.size()) / 2;
// 如果合并后的数组长度为奇数，中位数就是中间的那个元素
if ((nums1.size() + nums2.size()) % 2 == 1) {
return double(merge[mid]); // 返回 merge[mid]，直接返回该值
} else {
// 如果合并后的数组长度为偶数，中位数是中间两个数的平均值
return double(merge[mid - 1] + merge[mid]) / 2; // 计算并返回平均值
}
}
};
代码实现（思路二（划分数组（二分查找）））：
class Solution2 {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
// 确保 nums1 是较小的数组，以减少二分查找的次数
if (nums1.size() > nums2.size()) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.size(); // nums1 的大小
int n = nums2.size(); // nums2 的大小
int left = 0, right = m; // 在 nums1 数组上进行二分查找的左、右边界
// 使用二分查找在较小的数组 nums1 中查找合适的分区
while (left <= right) {
// 计算 nums1 的分区点
int partition1 = (left + right) / 2;
// 计算 nums2 的分区点，使得左右两部分元素数量相等或相差1
int partition2 = (m + n + 1) / 2 - partition1;
// 计算分区后的左右部分的最大值和最小值
// nums1 左侧最大值
int maxLeft1 = (partition1 == 0) ? INT_MIN : nums1[partition1 - 1];
// nums1 右侧最小值
int minRight1 = (partition1 == m) ? INT_MAX : nums1[partition1];
// nums2 左侧最大值
int maxLeft2 = (partition2 == 0) ? INT_MIN : nums2[partition2 - 1];
// nums2 右侧最小值
int minRight2 = (partition2 == n) ? INT_MAX : nums2[partition2];
// 判断分区是否有效
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
// 有效分区，计算中位数
if ((m + n) % 2 == 0) {
// 如果总元素个数是偶数，中位数为左右最大值和最小值的平均值
return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0;
} else {
// 如果总元素个数是奇数，中位数为左侧的最大值
return max(maxLeft1, maxLeft2);
}
}
// 如果 maxLeft1 > minRight2，说明 partition1 太大，需要向左缩小
else if (maxLeft1 > minRight2) {
right = partition1 - 1; // 调整右边界
}
// 如果 maxLeft2 > minRight1，说明 partition1 太小，需要向右扩大
else {
left = partition1 + 1; // 调整左边界
}
}
// 如果没有找到合适的中位数，代码逻辑应达到这里，可能代表输入不符合条件
return 0.0; // 通过编译需要添加返回值
}
};
以思路二为例进行调试
#include<iostream>
#include <vector>
#include <algorithm>
using namespace std;
class Solution2 {
public:
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
// 确保 nums1 是较小的数组，以减少二分查找的次数
if (nums1.size() > nums2.size()) {
return findMedianSortedArrays(nums2, nums1);
}
int m = nums1.size(); // nums1 的大小
int n = nums2.size(); // nums2 的大小
int left = 0, right = m; // 在 nums1 数组上进行二分查找的左、右边界
// 使用二分查找在较小的数组 nums1 中查找合适的分区
while (left <= right) {
// 计算 nums1 的分区点
int partition1 = (left + right) / 2;
// 计算 nums2 的分区点，使得左右两部分元素数量相等或相差1
int partition2 = (m + n + 1) / 2 - partition1;
// 计算分区后的左右部分的最大值和最小值
// nums1 左侧最大值
int maxLeft1 = (partition1 == 0) ? INT_MIN : nums1[partition1 - 1];
// nums1 右侧最小值
int minRight1 = (partition1 == m) ? INT_MAX : nums1[partition1];
// nums2 左侧最大值
int maxLeft2 = (partition2 == 0) ? INT_MIN : nums2[partition2 - 1];
// nums2 右侧最小值
int minRight2 = (partition2 == n) ? INT_MAX : nums2[partition2];
// 判断分区是否有效
if (maxLeft1 <= minRight2 && maxLeft2 <= minRight1) {
// 有效分区，计算中位数
if ((m + n) % 2 == 0) {
// 如果总元素个数是偶数，中位数为左右最大值和最小值的平均值
return (max(maxLeft1, maxLeft2) + min(minRight1, minRight2)) / 2.0;
} else {
// 如果总元素个数是奇数，中位数为左侧的最大值
return max(maxLeft1, maxLeft2);
}
}
// 如果 maxLeft1 > minRight2，说明 partition1 太大，需要向左缩小
else if (maxLeft1 > minRight2) {
right = partition1 - 1; // 调整右边界
}
// 如果 maxLeft2 > minRight1，说明 partition1 太小，需要向右扩大
else {
left = partition1 + 1; // 调整左边界
}
}
// 如果没有找到合适的中位数，代码逻辑应达到这里，可能代表输入不符合条件
return 0.0; // 通过编译需要添加返回值
}
};
int main(int argc, char const *argv[])
{
vector<int> nums1={1,2};
vector<int> nums2={3,4};
Solution2 s2;
cout<<s2.findMedianSortedArrays(nums1,nums2);
return 0;
}
寻找两个正序数组的中位数（68_4)原题链接
欢迎大家和我沟通交流(✿◠‿◠)