原题链接

LeetCode 4

在题目： 寻找两个有序数组的第K个数的基础上有扩展

二分查找

给定两个有序数组，要求找到两个有序数组的中位数，最直观的思路有以下两种：

• 使用归并的方式，合并两个有序数组，得到一个大的有序数组。大的有序数组的中间位置的元素，即为中位数。

• 不需要合并两个有序数组，只要找到中位数的位置即可。由于两个数组的长度已知，因此中位数对应的两个数组的下标之和也是已知的。维护两个指针，初始时分别指向两个数组的下标 $0$ 的位置，每次将指向较小值的指针后移一位（如果一个指针已经到达数组末尾，则只需要移动另一个数组的指针），直到到达中位数的位置。

假设两个有序数组的长度分别为 $m$ 和 $n$，上述两种思路的复杂度如何？

第一种思路的时间复杂度是 $O(m+n)$，空间复杂度是 $O(m+n)$。第二种思路虽然可以将空间复杂度降到 $O(1)$，但是时间复杂度仍是 $O(m+n)$。

如何把时间复杂度降低到 $O(\log(m+n))$ 呢？如果对时间复杂度的要求有 $\log$，通常都需要用到二分查找，这道题也可以通过二分查找实现。

根据中位数的定义，当 $m+n$ 是奇数时，中位数是两个有序数组中的第 $(m+n)/2$ 个元素，当 $m+n$ 是偶数时，中位数是两个有序数组中的第 $(m+n)/2$ 个元素和第 $(m+n)/2+1$ 个元素的平均值。因此，这道题可以转化成寻找两个有序数组中的第 $k$ 小的数，其中 $k$ 为 $(m+n)/2$ 或 $(m+n)/2+1$。

假设两个有序数组分别是 $\text{A}$ 和 $\text{B}$。要找到第 $k$ 个元素，我们可以比较 $\text{A}[k/2-1]$ 和 $\text{B}[k/2-1]$，其中 $/$ 表示整数除法。由于 $\text{A}[k/2-1]$ 和 $\text{B}[k/2-1]$ 的前面分别有 $\text{A}[0\,..\,k/2-2]$ 和 $\text{B}[0\,..\,k/2-2]$，即 $k/2-1$ 个元素，对于 $\text{A}[k/2-1]$ 和 $\text{B}[k/2-1]$ 中的较小值，最多只会有 $(k/2-1)+(k/2-1) \leq k-2$ 个元素比它小，那么它就不能是第 $k$ 小的数了。

因此我们可以归纳出三种情况：

• 如果 $\text{A}[k/2-1] < \text{B}[k/2-1]$，则比 $\text{A}[k/2-1]$ 小的数最多只有 $\text{A}$ 的前 $k/2-1$ 个数和 $\text{B}$ 的前 $k/2-1$ 个数，即比 $\text{A}[k/2-1]$ 小的数最多只有 $k-2$ 个，因此 $\text{A}[k/2-1]$ 不可能是第 $k$ 个数，$\text{A}[0]$ 到 $\text{A}[k/2-1]$ 也都不可能是第 $k$ 个数，可以全部排除。

• 如果 $\text{A}[k/2-1] > \text{B}[k/2-1]$，则可以排除 $\text{B}[0]$ 到 $\text{B}[k/2-1]$。

• 如果 $\text{A}[k/2-1] = \text{B}[k/2-1]$，则可以归入第一种情况处理。

可以看到，比较 $\text{A}[k/2-1]$ 和 $\text{B}[k/2-1]$ 之后，可以排除 $k/2$ 个不可能是第 $k$ 小的数，查找范围缩小了一半。同时，我们将在排除后的新数组上继续进行二分查找，并且根据我们排除数的个数，减少 $k$ 的值，这是因为我们排除的数都不大于第 $k$ 小的数。

有以下三种情况需要特殊处理：

• 如果 $\text{A}[k/2-1]$ 或者 $\text{B}[k/2-1]$ 越界，那么我们可以选取对应数组中的最后一个元素。在这种情况下，我们必须根据排除数的个数减少 $k$ 的值，而不能直接将 $k$ 减去 $k/2$。

• 如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第 $k$ 小的元素。

• 如果 $k=1$，我们只要返回两个数组首元素的最小值即可。

用一个例子说明上述算法。假设两个有序数组如下：

A: 1 3 4 9
B: 1 2 3 4 5 6 7 8 9

两个有序数组的长度分别是 $4$ 和 $9$，长度之和是 $13$，中位数是两个有序数组中的第 $7$ 个元素，因此需要找到第 $k=7$ 个元素。

比较两个有序数组中下标为 $k/2-1=2$ 的数，即 $\text{A}[2]$ 和 $\text{B}[2]$，如下面所示：

A: 1 3 4 9
       ↑
B: 1 2 3 4 5 6 7 8 9
       ↑

由于 $\text{A}[2] > \text{B}[2]$，因此排除 $\text{B}[0]$ 到 $\text{B}[2]$，即数组 $\text{B}$ 的下标偏移（offset）变为 $3$，同时更新 $k$ 的值：$k=k-k/2=4$。

下一步寻找，比较两个有序数组中下标为 $k/2-1=1$ 的数，即 $\text{A}[1]$ 和 $\text{B}[4]$，如下面所示，其中方括号部分表示已经被排除的数。

A: 1 3 4 9
     ↑
B: [1 2 3] 4 5 6 7 8 9
             ↑

由于 $\text{A}[1] < \text{B}[4]$，因此排除 $\text{A}[0]$ 到 $\text{A}[1]$，即数组 $\text{A}$ 的下标偏移变为 $2$，同时更新 $k$ 的值：$k=k-k/2=2$。

下一步寻找，比较两个有序数组中下标为 $k/2-1=0$ 的数，即比较 $\text{A}[2]$ 和 $\text{B}[3]$，如下面所示，其中方括号部分表示已经被排除的数。

A: [1 3] 4 9
         ↑
B: [1 2 3] 4 5 6 7 8 9
           ↑

由于 $\text{A}[2]=\text{B}[3]$，根据之前的规则，排除 $\text{A}$ 中的元素，因此排除 $\text{A}[2]$，即数组 $\text{A}$ 的下标偏移变为 $3$，同时更新 $k$ 的值： $k=k-k/2=1$。

由于 $k$ 的值变成 $1$，因此比较两个有序数组中的未排除下标范围内的第一个数，其中较小的数即为第 $k$ 个数，由于 $\text{A}[3] > \text{B}[3]$，因此第 $k$ 个数是 $\text{B}[3]=4$。

A: [1 3 4] 9
           ↑
B: [1 2 3] 4 5 6 7 8 9
           ↑

复杂度分析

• 时间复杂度：$O(\log(m+n))$，其中 $m$ 和 $n$ 分别是数组 $\textit{nums}_1$ 和 $\textit{nums}_2$ 的长度。初始时有 $k=(m+n)/2$ 或 $k=(m+n)/2+1$，每一轮循环可以将查找范围减少一半，因此时间复杂度是 $O(\log(m+n))$。

• 空间复杂度：$O(1)$。

function findMedianSortedArrays(nums1: number[], nums2: number[]): number {

   const findKthElement = (k: number): number => {
        const len1 = nums1.length;
        const len2 = nums2.length;
        let i = 0;
        let j = 0;
        while(true) {
            if(i === len1) {
                return nums2[j + k - 1];
            }
            if(j === len2) {
                return nums1[i + k - 1];
            }
            if(k === 1) {
                return Math.min(nums1[i], nums2[j]);
            }

            let mid = Math.floor(k / 2); // 第二分之K个元素
            const compareIndex1 = Math.min(i + mid, len1) - 1; // 对应的下标
            const compareIndex2 = Math.min(j + mid, len2) - 1;

            // 比较
            if(nums1[compareIndex1] <= nums2[compareIndex2]) {
                // 排除nums1前半部分 长度为 array1Index - i + 1
                k -= (compareIndex1 - i + 1);
                i = compareIndex1 + 1;
            } else {
                k -= (compareIndex2 - j + 1);
                j = compareIndex2 + 1;
            }
        }
   } 


   const len1 = nums1.length;
   const len2 = nums2.length;
   const len = len1 + len2;
   if(len % 2 === 0) {
       // 偶数个数 中位数是第len/ 2 + 1个 和 第len / 2个
       const k1 = len / 2 + 1;
       const k2 = len / 2;
       const mid = (findKthElement(k1) + findKthElement(k2)) / 2;
       return mid
   } else {
       // 奇数个
       const k = Math.floor(len / 2) + 1;
       const mid = findKthElement(k);
       return mid;
   }
};