#yyds干货盘点# 算法突击之巧解中位数

浅沫记忆

今日题目
给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
示例 1：
输入：nums1 = [1,3], nums2 = [2]
输出：2.00000
解释：合并数组 = [1,2,3] ，中位数 2
示例 2：
输入：nums1 = [1,2], nums2 = [3,4]
输出：2.50000
解释：合并数组 = [1,2,3,4] ，中位数 (2 + 3) / 2 = 2.5
示例 3：
输入：nums1 = [0,0], nums2 = [0,0]
输出：0.00000
示例 4：
输入：nums1 = [], nums2 = [1]
输出：1.00000
示例 5：
输入：nums1 = [2], nums2 = []
输出：2.00000
提示：
nums1.length == m
nums2.length == n
0 <= m <= 1000
0 <= n <= 1000
1 <= m + n <= 2000
-106 <= nums1, nums2 <= 106
进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

思路
这是力扣前五题中唯一一道的难度为困难的题目。
首先再确认下中位数的定义：

如果某个有序数组长度是奇数，那么其中位数就是最中间那个，
如果是偶数，那么就是最中间两个数字的平均值

如果是在真实业务开发中，一般是内存不会太多限制，实现尽量容易理解，所以比较常见的实现方式是
先构造一个新的数组，存放两个数组，然后排序，最后找到中位数
这种方式充分利用现有api的方法，算法复杂度也取决于选择的api排序复杂度

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
  int[] nums = new int[nums1.length + nums2.length]; 
  for(int i = 0; i< nums1.length; i++){
    nums[i] = nums1[i];
  }
  for(int j = 0; j< nums2.length; j++){
    nums[nums1.length + j] = nums2[j];
  }
  Arrays.sort(nums);
  if(nums.length%2==0){
    return (nums[nums.length/2-1] + nums[nums.length/2])/2.0;
  }
  return nums[(nums.length-1)/2]/1.0;
}

执行用时：2 ms, 在所有 Java 提交中击败了99.33%的用户
内存消耗：39.6 MB, 在所有 Java 提交中击败了65.18%的用户

看一下JDK8中sort方法的注释

/**
   * Sorts the specified array into ascending numerical order.
   *
   * <p>Implementation note: The sorting algorithm is a Dual-Pivot Quicksort
   * by Vladimir Yaroslavskiy, Jon Bentley, and Joshua Bloch. This algorithm
   * offers O(n log(n)) performance on many data sets that cause other
   * quicksorts to degrade to quadratic performance, and is typically
   * faster than traditional (one-pivot) Quicksort implementations.
   *
   * @param a the array to be sorted
   */
public static void sort(int[] a) {

这个方法在元素少于286时使用得是快速排序，大于时使用得优化版的归并排序

时间复杂度都是O(n log(n))
所以这这种解法后的整体时间复杂度是O((n+m) log(n+m))

进阶
设计一个时间复杂度为 O(log (m+n)) 的算法
看见这个时间复杂度的要求，一般会联想到二分查找的算法
这道题采用类似二分查找的思想，主要是想办法找到中位数的分割线
官方题解很是很难理解的，需要多看几遍才能知道其中的意图
大体思想：

• 利用二分查找思想两个有序数组中位数的分割线，中位数只与分割线左右两侧的元素有关，偶数时取左右之和除以2，奇数时取左边最大
  
• 分割线满足的特点：左右两边元素个数相等（利用除法向下取证的特性，归纳出同一个公式， （m+n+1）/，从而忽略两个数组长度之和奇偶性的差异）
  
• 分割线左边所有元素 小于等于 分割线右边所有元素，由于分割线两边元素个数相等，挪动分割线就会有此消彼长的现象，这就是二分查找的思想
  

public double findMedianSortedArrays2(int[] nums1, int[] nums2) {
  int leftLength = nums1.length;
  int rightLength = nums2.length;
  // 为了保证第一个数组比第二个数组小(或者相等)
  if (leftLength > rightLength) {
    return findMedianSortedArrays2(nums2, nums1);
  }
  // 分割线左边的所有元素需要满足的个数 m + (n - m + 1) / 2;
  // 两个数组长度之和为偶数时，当在长度之和上+1时，由于整除是向下取整，所以不会改变结果
  // 两个数组长度之和为奇数时，按照分割线的左边比右边多一个元素的要求，此时在长度之和上+1，就会被2整除，会在原来的数
  //的基础上+1，于是多出来的那个1就是左边比右边多出来的一个元素
  int totalLeft = (leftLength + rightLength + 1) / 2;
  // 在 nums1 的区间 [0, leftLength] 里查找恰当的分割线，
  // 使得 nums1[i - 1] <= nums2[j] && nums2[j - 1] <= nums1[i]
  int left = 0;
  int right = leftLength;
  // nums1[i - 1] <= nums2[j]
  //  此处要求第一个数组中分割线的左边的值 不大于(小于等于) 第二个数组中分割线的右边的值
  // nums2[j - 1] <= nums1[i]
  //  此处要求第二个数组中分割线的左边的值 不大于(小于等于) 第一个数组中分割线的右边的值
  // 循环条件结束的条件为指针重合，即分割线已找到
  while (left < right) {
    // 二分查找，此处为取第一个数组中左右指针下标的中位数，决定起始位置
    // 此处+1首先是为了不出现死循环，即left永远小于right的情况
    // left和right最小差距是1，此时下面的计算结果如果不加1会出现i一直=left的情况，而+1之后i才会=right
    // 于是在left=i的时候可以破坏循环条件，其次下标+1还会保证下标不会越界，因为+1之后向上取整，保证了
    // i不会取到0值，即i-1不会小于0
    // 此时i也代表着在一个数组中左边的元素的个数
    int i = left + (right - left + 1) / 2;
    // 第一个数组中左边的元素个数确定后，用左边元素的总和-第一个数组中元素的总和=第二个元素中左边的元素的总和
    // 此时j就是第二个元素中左边的元素的个数
    int j = totalLeft - i;
    // 此处用了nums1[i - 1] <= nums2[j]的取反，当第一个数组中分割线的左边的值大于第二个数组中分割线的右边的值
    // 说明又指针应该左移，即-1
    if (nums1[i - 1] > nums2[j]) {
      // 下一轮搜索的区间 [left, i - 1]
      right = i - 1;
      // 此时说明条件满足，应当将左指针右移到i的位置，至于为什么是右移，请看i的定义
    } else {
      // 下一轮搜索的区间 [i, right]
      left = i;
    }
  }
  // 退出循环时left一定等于right，所以此时等于left和right都可以
  // 为什么left一定不会大于right?因为left=i。
  // 此时i代表分割线在第一个数组中所在的位置
  // nums1[i]为第一个数组中分割线右边的第一个值
  // nums[i-1]即第一个数组中分割线左边的第一个值
  int i = left;
  // 此时j代表分割线在第二个数组中的位置
  // nums2[j]为第一个数组中分割线右边的第一个值
  // nums2[j-1]即第一个数组中分割线左边的第一个值
  int j = totalLeft - i;
  // 当i=0时，说明第一个数组分割线左边没有值，为了不影响
  // nums1[i - 1] <= nums2[j] 和 Math.max(nums1LeftMax, nums2LeftMax)
  // 的判断，所以将它设置为int的最小值
  int nums1LeftMax = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
  // 等i=第一个数组的长度时，说明第一个数组分割线右边没有值，为了不影响
  // nums2[j - 1] <= nums1[i] 和 Math.min(nums1RightMin, nums2RightMin)
  // 的判断，所以将它设置为int的最大值
  int nums1RightMin = i == leftLength ? Integer.MAX_VALUE : nums1[i];
  // 当j=0时，说明第二个数组分割线左边没有值，为了不影响
  // nums2[j - 1] <= nums1[i] 和 Math.max(nums1LeftMax, nums2LeftMax)
  // 的判断，所以将它设置为int的最小值
  int nums2LeftMax = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
  // 等j=第二个数组的长度时，说明第二个数组分割线右边没有值，为了不影响
  // nums1[i - 1] <= nums2[j] 和 Math.min(nums1RightMin, nums2RightMin)
  // 的判断，所以将它设置为int的最大值
  int nums2RightMin = j == rightLength ? Integer.MAX_VALUE : nums2[j];
  // 如果两个数组的长度之和为奇数，直接返回两个数组在分割线左边的最大值即可
  if (((leftLength + rightLength) % 2) == 1) {
    return Math.max(nums1LeftMax, nums2LeftMax);
  } else {
    // 如果两个数组的长度之和为偶数，返回的是两个数组在左边的最大值和两个数组在右边的最小值的和的二分之一
    // 此处不能被向下取整，所以要强制转换为double类型
    return (double) ((Math.max(nums1LeftMax, nums2LeftMax) + Math.min(nums1RightMin, nums2RightMin))) / 2;
  }
}

小结
这道题需要按照算法复杂度的要求实现，还是很有难度的，需要大量思考归纳公式，同时代码实现时还要充分考虑边界问题，相当有难度。