关于算法:每日一题寻找两个正序数组的中位数

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 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1[i], nums2[i] <= 106

二分查找

题目要求工夫复杂度为 O(log(m+n))，且数组有序，可采纳二分求解，具体做法如下：

当 m + n 为奇数时，题目等价于找到第 k 小的元素，当 m + n 为偶数时，题目等价于找到第 k 和 k + 1 小的数。故，工作就是找到第 k 小的数，若 m + n 为偶数，则在第 k 小的数前面再思考一个数即可。

1. 设 i =0，j=0，ti，tj，i 示意数组 A 的起始思考地位，也即 A 以后思考 A[i..m-1]，相似的，B 以后思考 B[j..n-1]，ti 和 tj 别离示意 A 和 B 的下一个起始思考地位
2. 令 ti = i+k/2，tj = j+k/2，ti、tj 别离不能超过 m、n

3. 对于数组 A[i..m-1]、B[j..n-1]，思考 A[ti-1]和 B[tj-1]

   • 若 A[ti-1]
   • 若 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]

循环完结条件

• 当 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<int> &nums1, vector<int> &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] < B[j])
                return (A[i] + (i == m - 1 ? B[j] : min(A[i + 1], B[j])))/2.0;
            else
                return (B[j] + (j == n - 1 ? A[i] : min(B[j + 1], A[i])))/2.0;
        }
        // 二分
        ti = min(i + (k >> 1), m), tj = min(j + (k >> 1), n);
        if (A[ti-1] <= B[tj-1]) {k -= ti - i, i = ti;} else
            k -= tj - j, j = tj;
    }
}

工夫复杂度：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<int> &nums1, vector<int> &nums2) {auto res=[&](vector<int> &A,vector<int> &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 <= rb && lb <= ra) {if (fg) return (double)max(la, lb);
                return (max(la, lb) + min(ra, rb)) / 2.0;
            }
                // 放大范畴
            else if (la <= rb)l = i;
            else r = i - 1;
        }
    };
    return nums1.size() > nums2.size() ? res(nums2, nums1) : res(nums1, nums2);
}

工夫复杂度：O(log(min(m,n)))

空间复杂度：O(1)