LeetCode 热题 100_寻找两个正序数组的中位数（68_4_困难_C++）(二分查找)（先合并再挑选中位数；划分数组（二分查找））

题目描述：

给定两个大小分别为 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
-10⁶ <= nums1[i], nums2[i] <= 10⁶

题解：

解题思路：

思路一（先合并再挑选中位数）：

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 用于遍历合并后的数组 mergeint 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 的分区点，使得左右两部分元素数量相等或相差1int 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 的分区点，使得左右两部分元素数量相等或相差1int 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)原题链接
欢迎大家和我沟通交流(✿◠‿◠)