【数学|4. 寻找两个正序数组的中位数】要求：O(log(m+n))
思路：分割线将两个数组划分，奇数时左边多一个，因此左边个数是(m+n+1)/2=k，分隔线右边元素下标i+j=k
在小数组二分否则k-i越界
满足交叉小于等于，二分查找使得a[i]>=b[j-1]，那么如何使的a[i-1]<=b[j]？答案是j右移i左移，即我们只需要在a[i]>=b[j-1]时左移i即可
最后看注释，边界简单
class Solution {
public:
double findMedianSortedArrays(vector& nums1, vector& nums2) {
int m=nums1.size(),n=nums2.size();
if(m>n)return findMedianSortedArrays(nums2,nums1);
int k=(m+n+1)/2;
int left=0,right=m-1;
while(left<=right){
int i=(left+right)/2;
int j=k-i;
if(nums1[i]>=nums2[j-1])right=i-1;
else left=i+1;
}
//right是第一个数组分隔线左边，第二个数组分割线左边是k-i-2
int l1=right,l2=k-l1-2,r1=l1+1,r2=l2+1;
int mid1;
if(l1==-1)mid1=nums2[l2];
else if(l2==-1)mid1=nums1[l1];
else mid1=max(nums1[l1],nums2[l2]);
if((m+n)&1)return mid1;
int mid2;
if(r1==m)mid2=nums2[r2];
else if(r2==n)mid2=nums1[r1];
else mid2=min(nums1[r1],nums2[r2]);
return (mid2+mid1)/2.0;
}
};
推荐阅读
- 蓝桥杯练习|试题 算法训练 台阶问题
- 算法题——字符串3.19
- 蓝桥杯|蓝桥杯AcWing学习笔记 4-3排序的学习（附相关蓝桥真题（小朋友排队）(Java)）
- #|蓝桥杯31天冲刺打卡题解（Day10）
- 蓝桥杯|蓝桥冲刺31天打卡—Day11
- #|蓝桥杯31天冲刺打卡题解（Day4）
- #|蓝桥杯31天冲刺打卡题解（Day11）
- LeetCode编程题解法汇总|力扣解法汇总606-根据二叉树创建字符串
- 蓝桥杯准备每日练习|【蓝桥杯方法篇】贪心算法详解一