题解|#4. 寻找两个正序数组的中位数#

• 中位数则取中间的两位数字平均值
  • 偶数：比如8，中间数分别是4和5。一半是4.5。
  • 奇数：比如7，中间数分别是4和4。一半是3.5。
  • 左边：要使7和8都能得到4。(7+1)/2和(8+1)/2
  • 右边：要使7和8都能得到5。7/2 + 1和8/2 + 1
  • left: (n+1)>>1
  • right: n>>1 + 1
• 问题的核心在于，如何快速找到第k位数
• 题目要求时间复杂度是O(log(m+n))，则应该联想到二分

核心逻辑：寻找两个正序数组的第k位

• 有两个数组A，B。大小分别是m，n。
• 先比较两个数组的第k/2个元素。A[k/2 - 1] 与 B[k/2 - 1]。
  • 比较出大小后，就可以至少去除k/2个元素了
  • A[k/2 - 1] < B[k/2 - 1]：至少排除A[0] ~ A[k/2 - 1]共k/2个元素。理想情况下，最多时存在B[0] ~ B[k/2 - 2] < B[k/2 - 1]共k/2 - 1个元素。总共k - 1个
• 边界情况
  • k=1：k/2-1 >= 0，所以以下的比较，k至少为1。比较两个数组的左边界
  • 越界：为了确保使用最小值比较，此时应该选用左边界进行比较。如果是小于，应该左边界右移一位,k只能减小一位
  • 边界到达数组的边缘。使用另一个数组

package pers.sloera.leetcode.findMedianSortedArrays;

/**
 * 4. 寻找两个正序数组的中位数
 * <p>
 * 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。
 * <p>
 * 请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。
 * <p>
 * 你可以假设 nums1 和 nums2 不会同时为空。
 * <p>
 * <p>
 * <p>
 * 示例 1:
 * <p>
 * nums1 = [1, 3]
 * nums2 = [2]
 * <p>
 * 则中位数是 2.0
 * 示例 2:
 * <p>
 * nums1 = [1, 2]
 * nums2 = [3, 4]
 * <p>
 * 则中位数是 (2 + 3)/2 = 2.5
 *
 * @author SloeraN
 * @version 1.0
 * @class pers.sloera.leetcode.findMedianSortedArrays.Solution
 * @date 2020/9/13
 */
public class Solution {

  public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    return findMedianSortedArrays1(nums1, nums2);
  }

  /**
   * 使用二分
   * <p>
   * 将题目转换成寻找两个有序数组中第k(从1开始)小的数字
   *
   * @param nums1 源数组1
   * @param nums2 源数组2
   * @return double 中位数
   * @date 2020/9/13
   */
  public double findMedianSortedArrays1(int[] nums1, int[] nums2) {
    int sum = nums1.length + nums2.length;
    // int left = findK(nums1, nums2, ((sum - 1) >> 1) + 1);
    int left = findK(nums1, nums2, ((sum + 1) >> 1));
    int right = findK(nums1, nums2, (sum >> 1) + 1);
    return (left + right) / 2.0;
  }

  /**
   * 寻找nums1和nums2第k位元素（升序排序）
   *
   * <p>
   * 比较思路：<br/>
   * 要获得第k个值，两个数组比较 k/2 - 1 位置的值，则可去除0~ k/2 - 1 = k/2个数值。通过左移数组的边界去除。
   * A[k/2-1]<B[k/2-1]。则极限情况为A[0]~A[k/2-1]=k/2与B[0]~B[k/2-2]=k/2-1 共k-1个比B[k/2 -1]小的。
   * 有可能第k位在A[k/2]~A[length-1]中，去除A[0]~A[k/2-1]中肯定不包含第k小的数字。
   * </p>
   *
   * <p>
   * 边界处理：
   * <ol>
   * <li>当存在数组左边界 = 数组长度时，说明此数组已排除完，使用另一个数组</li>
   * <li>当k=1时，只需要比较两个数组的左边界，返回最小值</li>
   * <li>当数组越界时，使用左边界值，保证此值是最小，排除的时候，k减小1.</li>
   * <li>比较后：移动较小值所在数组的左边界，减小对应的k值</li>
   * </ol>
   * </p>
   *
   * @param leftNums 源数组1
   * @param rightNums 源数组2
   * @param k 位置，从1开始计算
   * @return 第k位数值（升序）
   */
  private int findK(int[] leftNums, int[] rightNums, int k) {
    // 两个数组的左边界。通过移动数组左边界来排除较小的数
    int leftLeft = 0, leftRight = 0;
    for (; ; ) {
      // 一个为空，取另一个
      if (leftLeft >= leftNums.length) {
        return rightNums[leftRight + k - 1];
      }
      if (leftRight >= rightNums.length) {
        return leftNums[leftLeft + k - 1];
      }
      // 为1时，只需返回两个数组边界中的较小值
      if (k == 1) {
        return Math.min(leftNums[leftLeft], rightNums[leftRight]);
      }
      // 数组1待查找的坐标
      int indexLeft = leftLeft + k / 2 - 1;
      int stepLeft = k / 2;
      // 越界
      if (indexLeft >= leftNums.length) {
        indexLeft = leftLeft;
        stepLeft = 1;
      }
      // 数组2待查找的坐标
      int indexRight = leftRight + k / 2 - 1;
      int stepDown = k / 2;
      // 越界
      if (indexRight >= rightNums.length) {
        indexRight = leftRight;
        stepDown = 1;
      }
      if (leftNums[indexLeft] < rightNums[indexRight]) {
        //  排除无效
        leftLeft += stepLeft;
        k -= stepLeft;
      } else {
        leftRight += stepDown;
        k -= stepDown;
      }
    }
  }
}