LeetCode004-两个有序数组的中位数-最优算法代码讲解

最有帮助的视频讲解
【LeetCode004-两个有序数组的中位数-最优算法代码讲解】 https://www.bilibili.com/video/BV1H5411c7oC/?share_source=copy_web&vd_source=afbacdc02063c57e7a2ef256a4db9d2a
时间复杂度$O(log(min(m,n)))$
空间复杂度是$S(1)$

class Solution {
public:double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {int m = nums1.size() , n = nums2.size();if(m > n){return findMedianSortedArrays(nums2,nums1);}int iMin = 0 , iMax = m;while(iMin <= iMax){int i = iMin + iMax >> 1;int j = (m + n + 1) / 2 - i;//公式if(i != 0 && j != n && nums1[i - 1 ] > nums2[j]){iMax = i - 1;}else if(j != 0 && i != m && nums2[j - 1] > nums1[i]){iMin = i + 1;}else {int maxLf = 0;if(i == 0)maxLf = nums2[j - 1];else if(j == 0)maxLf = nums1[i - 1];elsemaxLf = max(nums1[i - 1],nums2[j - 1]);if((m + n)%2)return maxLf;int maxRg = 0;if(i == m)maxRg = nums2[j];else if(j == n)maxRg = nums1[i];else maxRg = min(nums1[i],nums2[j]);return (maxLf + maxRg) / 2.0;}}return 0.0;}
};