题目描述

题目链接

https://leetcode.cn/problems/median-of-two-sorted-arrays/

思路

1. 暴力思路

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

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

假设两个有序数组的长度分别为和，上述两种思路的复杂度如何？第一种思路的时间复杂度是，空间复杂度也是。第二种思路虽然可以将空间复杂度降到，但是时间复杂度仍是，不满足题目要求。

2. 二分思路

那如何把时间复杂度降低到呢？实际上，如果对时间复杂度的要求有，通常都需要用到二分查找，这道题也可以通过二分查找实现。

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

假设两个有序数组分别是和。要找到第个元素，我们可以比较和。由于和的前面分别有和，即个元素，对于和中的较小值，最多只会有个元素比它小，那么它就不可能是第小的数了。

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

• 如果，则比小的数最多只有的前个数和的前个数，即比小的数最多只有个，因此不可能是第个数，到也都不可能是第个数，可以全部排除。
• 如果，则可以排除到。
• 如果，则可以归入第一种情况处理。

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

在代码实现上，有以下三种情况需要特殊处理：

• 如果或者越界，那么我们可以选取对应数组中的最后一个元素。在这种情况下，我们必须根据排除数的个数减少的值，而不能直接将减去。
• 如果一个数组为空，说明该数组中的所有元素都被排除，我们可以直接返回另一个数组中第小的元素。
• 如果，我们只要返回两个数组首元素的最小值即可。

  3. 举例说明

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

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

  两个有序数组的长度分别是和，长度之和是，中位数是两个有序数组中的第个元素，因此需要找到第个元素。比较两个有序数组中下标为的数，即和，如下所示：

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

  由于，因此排除到，即数组的下标偏移（offset）变为，同时更新的值：。之后，继续比较两个有序数组中下标为的数，即和，如下所示，其中方括号部分表示已经被排除的数。

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

  由于，因此排除到，即数组的下标偏移变为，同时更新的值：。之后，继续比较两个有序数组中下标为的数，即比较和，如下所示，其中方括号部分表示已经被排除的数。

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

  由于，根据规则，需排除，即数组的下标偏移变为，同时更新的值：。由于的值变成，因此比较两个有序数组中的未排除下标范围内的第一个数，其中较小的数即为第个数，由于，因此第个数就是。

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

  代码实现

  ```java public double findMedianSortedArrays(int[] nums1, int[] nums2) { int total = nums1.length + nums2.length; if (total % 2 == 1) {

    // 奇数
    return getKthElement(nums1, nums2, total / 2 + 1);
  

  } else {

    // 偶数
    double a = getKthElement(nums1, nums2, total / 2);
    double b = getKthElement(nums1, nums2, total / 2 + 1);
    return (a + b) / 2D;
  

  } }

private int getKthElement(int[] nums1, int[] nums2, int k) { int index1 = 0, index2 = 0; while (true) { // num1数组里的元素全被排除了,直接返回num2中第k小的元素 if (index1 == nums1.length) { return nums2[index2 + k - 1]; } // num2数组里的元素全被排除了,直接返回num1中第k小的元素 if (index2 == nums2.length) { return nums1[index1 + k - 1]; } // 返回两个数组首元素的最小值 if (k == 1) { return Math.min(nums1[index1], nums2[index2]); } // 比较 A[k/2−1] 与 B[k/2−1],避免数组越界 int newIndex1 = Math.min(index1 + k / 2, nums1.length) - 1; int newIndex2 = Math.min(index2 + k / 2, nums2.length) - 1; if (nums1[newIndex1] <= nums2[newIndex2]) { // 计算实际减去的k值 k -= (newIndex1 - index1 + 1); // 更新数组offset index1 = newIndex1 + 1; } else { k -= (newIndex2 - index2 + 1); index2 = newIndex2 + 1; } } } ```

复杂度分析

• 时间复杂度：，其中和分别是数组和的长度。初始时有或，每一轮循环可以将查找范围减少一半，因此时间复杂度是。
• 空间复杂度：。