4. 寻找两个正序数组的中位数
关键词：二分查找、数组划分
题目来源：4. 寻找两个正序数组的中位数 – 力扣（Leetcode）
题目描述
T二分查找
T数组划分给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
算法的时间复杂度应该为 O(log (m+n)) 。
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 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 二分查找
题目要求时间复杂度为O(log(m+n))，且数组有序，可采用二分求解，具体做法如下：
当m+n为奇数时，题目等价于找到第k小的元素，当m+n为偶数时，题目等价于找到第k和k+1小的数。故，任务就是找到第k小的数，若m+n为偶数，则在第k小的数后面再考虑一个数即可。
- 设i=0，j=0，ti，tj，i表示数组A的起始考虑位置，也即A当前考虑A[i..m-1]，类似的，B当前考虑B[j..n-1]，ti和tj分别表示A和B的下一个起始考虑位置
- 令ti = i+k/2，tj = j+k/2，ti、tj分别不能超过m、n
-
对于数组A[i..m-1]、B[j..n-1]，考虑A[ti-1]和B[tj-1]
- 若A[ti-1]＜B[tj-1]，说明A[i..ti-1]必定不是第k小的数，也即可以排除A[i..ti-1]，共k/2个数。于是，令i = ti，k -= k/2。
- 若A[ti-1]＞B[tj-1]，说明B[j..tj-1]必定不是第k小的数，也即可以排除B[j..tj-1]，共k/2个数。于是，令j = tj，k -= k/2。
- 若A[i+k/2-1]＝B[j+k/2-1]，则可归为A[ti-1]＜B[tj-1]的情况
循环结束条件
- 当i=m时，m+n为偶数 ? return (B[j+k-1]+B[j+k])/2 : return min( B[j+k-1]+B[j+k] )
- 当j=n时，m+n为偶数 ? return (A[i+k-1]+A[i+k])/2 : return min( A[i+k-1]+A[i+k] )
- 当k=1时，m+n为偶数 ? return (A[i]+B[i])/2 : return min( A[i], B[i] )
double findMedianSortedArrays(vector &nums1, vector &nums2) {
auto &A = nums1, &B = nums2;
int m = A.size(), n = B.size(), k = (n + m + 1) >> 1;
int i = 0, j = 0, fg = (m + n) & 1, ti, tj;
while (true) {
// 循环出口
if (i == m)return fg ? B[j + k - 1] : (B[j + k - 1] + B[j + k]) / 2.0;
if (j == n)return fg ? A[i + k - 1] : (A[i + k - 1] + A[i + k]) / 2.0;
if (k == 1) {
if (fg)return min(A[i], B[j]);
if (A[i] > 1), m), tj = min(j + (k >> 1), n);
if (A[ti-1] 时间复杂度：O( log(m+n) )。每次循环都会排除k/2个数
空间复杂度：O(1)
数组划分
中位数性质：中位数将数组划分成两半，左半部分的数均小于等于右半部分的数。
利用中位数的上述性质，可得到如下做法：
设k=( m+n+1 )/2。
i将数组A划分为A[0..i-1]和A[i..m-1]两部分，其中，i=0时A[0..i-1]为空，i=m时A[i..m-1]为空。
j=k-i，j将数组B划分成B[0..j-1]和B[j..n-1]两部分，其中，j=0时B[0..j-1]为空，j=n时A[j..n-1]为空。
令L=A[0..i-1] + B[0..j-1]，R=A[i..m-1] + B[j..n-1]
考虑(m+n)为偶数的情况，L和R恰好各含有一半的元素。当L中的元素全小于等于R中的元素时，中位数=(max(L)+max(R))/2，而max(L)=max(A[i-1],B[j-1])，min(R)=min(A[i],B[j])。
L中的元素全小于R中的元素等价于A[i-1]≤B[j]且B[j-1]≤A[i]。
于是，可通过二分来确定i的值，也即划分点，当有A[i-1]≤B[j]且B[j-1]≤A[i]，说明已经找到中位数。
为确保j不会越界，也即使得j保持在区间[0..n]内，应时数组A的长度大于数组B。
考虑(m+n)为奇数的情况，因为L中含有k个元素，故中位数为max(L)。
double findMedianSortedArrays_4(vector &nums1, vector &nums2) {
auto res=[&](vector &A,vector &B){
int m = A.size(), n = B.size(), k = (n + m + 1) >> 1, fg = (m + n) & 1;
// 分界点可选范围[l..r]
int l = 0, r = m, i, j;
// 答案一定存在
while (true) {
// 左：A[0..i-1] B[0..j-1]
i = (l + r + 1) >> 1, j = k - i;
// 交界处的四个数
int la = i ? A[i - 1] : INT_MIN, ra = i != m ? A[i] : INT_MAX;
int lb = j ? B[j - 1] : INT_MIN, rb = j != n ? B[j] : INT_MAX;
// 符合条件
if (la nums2.size() ? res(nums2, nums1) : res(nums1, nums2);
} 时间复杂度：O(log(min(m,n)))
空间复杂度：O(1)
服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net
