LeetCode 4. 寻找两个有序数组的中位数（二分查找，难）

文章目录

1. 题目2. 解题2.1 合并数组2.2 优化2.1解法，双指针2.3 二分法（找第k个数）2.4 切分法

1. 题目

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。

请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为$O(log(m+n))$。

你可以假设 nums1 和 nums2 不会同时为空。

示例 1: nums1 = [1, 3] nums2 = [2] 则中位数是 2.0 示例 2: nums1 = [1, 2] nums2 = [3, 4] 则中位数是 (2 + 3)/2 = 2.5

来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/median-of-two-sorted-arrays 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. 解题

2.1 合并数组

合并两个数组，再取中位数时间和空间复杂度均为 O(m+n) class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int n1 = nums1.size(), n2 = nums2.size(), len; len = n1 + n2; vector<int> nv(len); int i = 0, j = 0, k = 0; while(i < n1 && j < n2) { if(nums1[i] < nums2[j]) nv[k++] = nums1[i++]; else nv[k++] = nums2[j++]; } if(i == n1) { while(j < n2) nv[k++] = nums2[j++]; } else { while(i < n1) nv[k++] = nums1[i++]; } if(len%2) return nv[len/2]; return (nv[len/2]+nv[len/2-1])/2.0; } };

2.2 优化2.1解法，双指针

不合并两个数组，设置双指针在两个数组上比较大小，分别移动各自的指针，遍历到中间的计数停止时间复杂度 O(m+n)，空间复杂度 O(1) class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int n1 = nums1.size(), n2 = nums2.size(), len; len = n1 + n2; vector<int> nv(len); int i = 0, j = 0, k, left = -1, right = -1; for(k = 0; k <= len/2; ++k) { left = right; if(i < n1 && (j >= n2 || nums1[i] < nums2[j])) right = nums1[i++]; else right = nums2[j++]; } if(len%2) return right; return (left+right)/2.0; } };

2.3 二分法（找第k个数）

参考链接，解法3

class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int n1 = nums1.size(), n2 = nums2.size(), len, kth; len = n1 + n2; kth = (len+1)/2; if(len%2) return findKth(nums1,0,n1-1,nums2,0,n2-1,kth); return (findKth(nums1,0,n1-1,nums2,0,n2-1,kth)+findKth(nums1,0,n1-1,nums2,0,n2-1,kth+1))/2.0; } int findKth(vector<int>& nums1, int s1, int e1, vector<int>& nums2, int s2, int e2, int kth) { int len1 = e1-s1+1; int len2 = e2-s2+1; if(len1 > len2) //确保传进来的参数len1是较短的数组(它先空) return findKth(nums2,s2,e2,nums1,s1,e1,kth); if(len1 == 0) return nums2[s2+kth-1];//一个为空，直接找到答案 if(kth == 1) return min(nums1[s1],nums2[s2]); int i = s1+min(len1,kth/2)-1;//min使得指针不会越界 int j = s2+min(len2,kth/2)-1; if(nums1[i] > nums2[j])//舍去nums2前面的 return findKth(nums1,s1,e1,nums2,j+1,e2,kth-(j-s2+1)); else//舍去nums1前面的 return findKth(nums1,i+1,e1,nums2,s2,e2,kth-(i-s1+1)); } };

$O(lg(m+n))$时间复杂度，尾递归，无需堆栈，空间复杂度 $O(1)$

2.4 切分法

放了方便处理，确保A数组长度较短初始状态下mid1取数组1的中间，mid1,mid2左半边的总个数 == 右半边 或者 比右半边少1对mid1进行二分查找，相应的mid2会随动（$mid2=allHalf-mid1$）如果 $lmax1<=rmin2,andlmax2<=rmin1$ , 成功找到分界线则 $Lmax=max(lmax1,lmax2))$, $Rmin=min(rmin1,rmin2)$，总个数为奇数返回$Rmin$, 偶数返回$(Lmax+Rmin)/2.0$ class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int n1 = nums1.size(), n2 = nums2.size(); if(n1 > n2)//确保n1是较短的数组 return findMedianSortedArrays(nums2, nums1); int left = 0, right = n1, allHalf = (n1+n2)/2, mid1, mid2; int lmax1, rmin1, lmax2, rmin2; while(left <= right) { mid1 = left+((right-left)>>1); mid2 = allHalf - mid1; lmax1 = (mid1-1 >= 0) ? nums1[mid1-1] : INT_MIN; rmin1 = (mid1 < n1) ? nums1[mid1] : INT_MAX; lmax2 = (mid2-1 >= 0) ? nums2[mid2-1] : INT_MIN; rmin2 = (mid2 < n2) ? nums2[mid2] : INT_MAX; //在边界处，认为没有元素，设置成最大或者最小，保证下面关系式成立 if(lmax1 > rmin2) right = mid1-1; else if(lmax2 > rmin1) left = mid1+1; else { left = right = mid1; break; } } int i = left, j = allHalf-left; int l = max( i-1 >= 0 ? nums1[i-1] : INT_MIN, j-1 >= 0 ? nums2[j-1] : INT_MIN); int r = min( i < n1 ? nums1[i] : INT_MAX, j < n2 ? nums2[j] : INT_MAX); if((n1+n2)%2 == 1) return r; return (l+r)/2.0; } };