力扣经典二分题：4. 寻找两个正序数组的中位数

题目链接：4. 寻找两个正序数组的中位数 - 力扣（LeetCode）

一、题目分析

• 这道题目是让我们在 两个正序的数组中寻找中位数
• 已知两个数组的大小分别是：int m = nums1.size(),n = nums2.size();
• 中位数性质1：中位数左侧元素 ≤ 中位数 且 中位数右侧元素 ≥ 中位数 （以升序来看）
• 中位数性质2：对于一个长度为 N 的数组，中位数将数组一分为二，使得左侧与右侧得元素长度差 ≤ 1
• 当 m + n 为奇数时，我们需要找到合并后数组中第 k + 1 小的元素，其中 k = (m + n) / 2。
• 当 m + n 为偶数时，我们需要找到合并后数组中第 k 和第 k + 1 小的元素，然后计算它们的平均值，其中 k = (m + n) / 2 - 1（注意这里 k 是基于 0 的索引，所以实际要找的元素位置是 k 和 k + 1）。

二、算法原理讲解

解法一：暴力排序

通过合并排序的原理，通过中位数的性质，可快速得到中位数的下标，较为简单

时间复杂度为O(M+N)，空间复杂度为O(M+N)

解法二：双指针 

时间复杂度为O(M+N)，空间复杂度为O(1)

解法三：暴力枚举

解法四：二分优化 

 

三、编写代码

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size(), n = nums2.size();if(m > n) swap(nums1,nums2); // 保证nums1始终是较短数组int k = (m + n + 1) / 2; // 应划分给小数组的个数// 枚举 i [0,m]for(int i = 0;i <= m;i++){int&& j = k - i;// 分割线周围的四个值int a = i == m ? INT_MAX :nums1[i];int b = i == 0 ? INT_MIN :nums1[i-1];cout << i << ' ' << j << endl;int c = j == n ? INT_MAX :nums2[j];int d = j == 0 ? INT_MIN :nums2[j-1];// 分割线是否合法if(b <= c && d <= a){if((m + n) % 2 == 1) return max(b,d);else return (double)(max(b,d) + min(c,a)) / 2;}}return 1314.521;}
};

 

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {// 保证nums1始终是较短数组if(nums1.size() > nums2.size()) swap(nums1,nums2);// 应划分给小数组的个数int k = (nums1.size() + nums2.size() + 1) / 2; // 枚举nums1数组中应该划分给小数组的元素个数（二分优化）int left = 0,right = nums1.size();while(left < right){// mid ∈ [0,m]int i = (left + right + 1) / 2; int j = k - i;cout << i << endl;if(nums1[i-1] <= nums2[j]) left = i;else right = i - 1;}// 分割线两边的值int a = left == nums1.size() ? INT_MAX :nums1[left];int b = left == 0 ? INT_MIN :nums1[left-1];int c = (k-left) == nums2.size() ? INT_MAX :nums2[k-left];int d = (k-left) == 0 ? INT_MIN :nums2[k-left-1];// 处理数据+返回if((nums1.size() + nums2.size()) % 2 == 1) return max(b,d);else return (double)(max(b,d) + min(c,a)) / 2;}
};