image.png

解题思路

image.png

  2.     public double findMedianSortedArrays(int[] nums1, int[] nums2) {
  3.         int m = nums1.length;
  4.         int n = nums2.length;
  5.         //处理任何一个nums为空数组的情况
  6.         if (m == 0) {
  7.             if (n % 2 != 0)
  8.                 return 1.0 * nums2[n / 2];
  9.             return (nums2[n / 2] + nums2[n / 2 - 1]) / 2.0;
  10.         }
  11.         if (n == 0) {
  12.             if (m % 2 != 0)
  13.                 return 1.0 * nums1[m / 2];
  14.             return (nums1[m / 2] + nums1[m / 2 - 1]) / 2.0;
  15.         }
  16.         int total = m + n;
  17.         //总数为奇数，找第 total / 2 + 1 个数
  18.         if ((total & 1) == 1) {
  19.             return find_kth(nums1, 0, nums2, 0, total / 2 + 1);
  20.         }
  21.         //总数为偶数，找第 total / 2 个数和第total / 2 + 1个数的平均值
  22.         return (find_kth(nums1, 0, nums2, 0, total / 2) + find_kth(nums1, 0, nums2, 0, total / 2 + 1)) / 2.0;
  23.     }
  25.     //寻找a 和 b 数组中，第k个数字
  26.     double find_kth(int[] a, int a_begin, int[] b, int b_begin, int k) {
  27.         //当a 或 b 超过数组长度，则第k个数为另外一个数组第k个数
  28.         if (a_begin >= a.length)
  29.             return b[b_begin + k - 1];
  30.         if (b_begin >= b.length)
  31.             return a[a_begin + k - 1];
  32.         //k为1时，两数组最小的那个为第一个数
  33.         if (k == 1)
  34.             return Math.min(a[a_begin], b[b_begin]);
  35.         int mid_a = Integer.MAX_VALUE;
  36.         int mid_b = Integer.MAX_VALUE;
  37.         //mid_a / mid_b 分别表示 a数组、b数组中第 k / 2 个数
  38.         if (a_begin + k / 2 - 1 < a.length)
  39.             mid_a = a[a_begin + k / 2 - 1];
  40.         if (b_begin + k / 2 - 1 < b.length)
  41.             mid_b = b[b_begin + k / 2 - 1];
  42.         //如果a数组的第 k / 2 个数小于b数组的第 k / 2 个数，表示总的第 k 个数位于 a的第k / 2个数的后半段，或者是b的第 k / 2个数的前半段
  43.         //由于范围缩小了 k / 2 个数，此时总的第 k 个数实际上等于新的范围内的第 k - k / 2个数，依次递归
  44.         if (mid_a < mid_b)
  45.             return find_kth(a, a_begin + k / 2, b, b_begin, k - k / 2);
  46.         //否则相反
  47.         return find_kth(a, a_begin, b, b_begin + k / 2, k - k / 2);
  48.     }