普通解法

  1.  public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
  2.         //合并两个有序数组
  3.         int n = nums1.length;
  4.         int m = nums2.length;
  5.         int[] nums = new int[m + n];
  6.         int index = nums.length;
  7.         while (m > 0 && n > 0) {
  8.             if (nums1[n - 1] >= nums2[m - 1]) {
  9.                 nums[--index] = nums1[--n];
  10.             } else {
  11.                 nums[--index] = nums2[--m];
  12.             }
  13.         }
  14.         while (n > 0) {
  15.             nums[--index] = nums1[--n];
  16.         }
  17.         while (m > 0) {
  18.             nums[--index] = nums2[--m];
  19.         }
  22.         //找中位数
  23.         if ((nums.length & 1) == 0) {
  24.             return (nums[nums.length/ 2] + nums[nums.length/ 2 - 1]) / 2.0;
  25.         } else {
  26.             return nums[nums.length/ 2];
  27.         }
  28.     }

最优解法

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

  • int _findKthNum ( _int[] arr1, int[] arr2, _int _kth )
    • int _getUpMedian ( _int[] A, int _s1, _int _e1, _int[] B, _int _s2, _int _e2 )
  • 函数getUpMedian 两个数组等长， 找上中位数
    • 1）偶数长度
      • 分三种情况， mid == mid’ mid > mid’ mid < mid’
        • 然后看哪些数不可能是上中位数，然后排除， 然后剩下的两个等长的继续迭代
    • 2）奇数长度
      • 也是跟上边一样分三种情况，不过具体某些情况需要手动扣掉一些数，保证长度一样然后能迭代
  1.  /*
  2.     A[s1...e1]
  3.     B[s2...e2]
  4.     这两段一定等长且都有序
  5.     求这两段整体的上中位数，上中位数值返回
  6.     */
  7.     public static int getUpMedian(int[] A, int s1, int e1, int[] B, int s2, int e2) {
  8.         int mid1 = 0;
  9.         int mid2 = 0;
  10.         // 每个数组至少两个数
  11.         while (s1 < e1) {
  12.             mid1 = (s1 + e1) >> 1;
  13.             mid2 = (s2 + e2) >> 1;
  14.             if (A[mid1] == B[mid2]) {
  15.                 return A[mid1];
  16.             }
  17.             if (((e1 - s1 + 1) & 1) == 0) { // 偶数长度
  18.                 // A[0,  1,  2,  3]
  19.                 // B[0‘, 1’, 2‘, 3’]
  20.                 // 里面的值代表下标
  21.                 // 上中位数就是第4位数
  22.                 if (A[mid1] > B[mid2]) { // 2, 3, 0', 1'排除
  23.                     e1 = mid1;
  24.                     s2 = mid2 + 1;
  25.                 } else { //反之
  26.                     e2 = mid2;
  27.                     s1 = mid1 + 1;
  28.                 }
  29.             } else { // 奇数长度
  30.                 // A[0,  1,  2,  3,  4]
  31.                 // B[0‘, 1’, 2‘, 3’, 4']
  32.                 // 上中位数就是第5位数
  33.                 if (A[mid1] > B[mid2]) {  // 2, 3, 4, 0', 1'排除
  34.                     if (B[mid2] >= A[mid1 - 1]) { // 手动抠一个， 若成立则找到了答案，返回
  35.                         return B[mid2];
  36.                     }
  37.                     //不成立的话，那我们的迭代潜台词（两个数组等长）就可以维持下去了
  38.                     e1 = mid1 - 1;
  39.                     s2 = mid2 + 1;
  40.                 } else { //反之
  41.                     if (A[mid1] >= B[mid2 - 1]) {
  42.                         return A[mid1];
  43.                     }
  44.                     e2 = mid2 - 1;
  45.                     s1 = mid1 + 1;
  46.                 }
  47.             }
  48.         }
  49.         // 此时退出了while循环，此刻条件s1 == e1, while循环里面没找到答案
  50.         // 说明每个数组此刻只剩一个数
  51.         // 那么上中位数就返回其中比较小的一个即可
  52.         return Math.min(A[s1], B[s2]);
  53.     }
  • 函数findKthNum ，两个数组可以不等长， 找第K小的数
    • 分三种情况
    • 1）1 ≤ K ≤ 短数组长度
      1. - 直接用算法原型getUpMedian
    • 2）短数组长度 < k ≤ 长数组长度
      1. - 短数组中所有的数都有可能
      2. - 长数组中的数部分有可能
      3. - 在长数组中可能的数部分中，手动扣掉一个后，才能用上我们的算法原型
    • 3）长数组长度＜K ＜ 两个数组的总长度
      1. - 特别注意
      2.    - 需要手动扣两个
      3.    - 排除的个数 +  。。。 =  Kth

image.png
image.png

  • 主函数调用 double _findMedianSortedArrays(_int[] nums1, int[] nums2) {
    • 判断两个数组总长度是奇数还是偶数，若是偶数就调用两次findKthNum函数然后平均下，若是奇数就调用一次findKthNum
  1.  //两个数组不等长， 找第K小的数
  2.     public static int findKthNum(int[] arr1, int[] arr2, int kth) {
  3.         int[] longs = arr1.length >= arr2.length ? arr1 : arr2;
  4.         int[] shorts = arr1.length < arr2.length ? arr1 : arr2;
  5.         int l = longs.length;
  6.         int s = shorts.length;
  7.         if (kth <= s) { //直接调算法原型
  8.             return getUpMedian(arr1, 0, kth - 1, arr2, 0, kth - 1);
  9.         } else if (kth > s && kth <= l) {
  10.             // 自己举例子，然后排除掉一些数， 最后再扣掉一个数，若是答案则返回，
  11.             // 否则，就可以使得两个范围的长度相等，调算法原型
  12.             if (longs[kth - s - 1] >= shorts[s - 1]) {
  13.                 return longs[kth - s - 1];
  14.             }
  15.             return getUpMedian(shorts, 0, s - 1, longs, kth - s, kth - 1);
  16.         } else {
  17.             // 自己举例子，然后排除掉一些数， 最后再扣掉二个数，若是答案则返回，
  18.             // 否则，就可以使得两个范围的长度相等，调算法原型
  19.             if (shorts[kth - l - 1] >= longs[l - 1]) {
  20.                 return shorts[kth - l - 1];
  21.             }
  22.             if (longs[kth - s - 1] >= shorts[s - 1]) {
  23.                 return longs[kth - s - 1];
  24.             }
  25.             return getUpMedian(shorts, kth - l, s - 1, longs, kth - s, l - 1);
  26.         }
  27.     }
  • 总代码 ```java public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    1.   int size = nums1.length + nums2.length;
    2.   boolean even = (size & 1) == 0;
    3.   if (nums1.length != 0 && nums2.length != 0) {
    4.       if (even) {
    5.           return (double) (findKthNum(nums1, nums2, size / 2) + findKthNum(nums1, nums2, size / 2 + 1)) / 2;
    6.       } else {
    7.           return findKthNum(nums1, nums2, size / 2 + 1);
    8.       }
    9.   } else if (nums1.length != 0) {
    10.       if (even) {
    11.           return (double) (nums1[(size - 1) / 2] + nums1[size / 2]) / 2;
    12.       } else {
    13.           return nums1[size / 2];
    14.       }
    15.   } else if (nums2.length != 0) {
    16.       if (even) {
    17.           return (double) (nums2[(size - 1) / 2] + nums2[size / 2]) / 2;
    18.       } else {
    19.           return nums2[size / 2];
    20.       }
    21.   } else {
    22.       return 0;
    23.   }
    } //两个数组不等长， 找第K小的数 public static int findKthNum(int[] arr1, int[] arr2, int kth) {
      int[] longs = arr1.length >= arr2.length ? arr1 : arr2;
  int[] shorts = arr1.length < arr2.length ? arr1 : arr2;
  int l = longs.length;
  int s = shorts.length;
  if (kth <= s) { //直接调算法原型
      return getUpMedian(arr1, 0, kth - 1, arr2, 0, kth - 1);
  } else if (kth > s && kth <= l) {
      // 自己举例子，然后排除掉一些数， 最后再扣掉一个数，若是答案则返回，
      // 否则，就可以使得两个范围的长度相等，调算法原型
      if (longs[kth - s - 1] >= shorts[s - 1]) {
          return longs[kth - s - 1];
      }
      return getUpMedian(shorts, 0, s - 1, longs, kth - s, kth - 1);
  } else {
      // 自己举例子，然后排除掉一些数， 最后再扣掉二个数，若是答案则返回，
      // 否则，就可以使得两个范围的长度相等，调算法原型
      if (shorts[kth - l - 1] >= longs[l - 1]) {
          return shorts[kth - l - 1];
      }
      if (longs[kth - s - 1] >= shorts[s - 1]) {
          return longs[kth - s - 1];
      }
      return getUpMedian(shorts, kth - l, s - 1, longs, kth - s, l - 1);
  }
    }
/*
A[s1...e1]
B[s2...e2]
这两段一定等长且都有序
求这两段整体的上中位数，上中位数值返回
*/
public static int getUpMedian(int[] A, int s1, int e1, int[] B, int s2, int e2) {
    int mid1 = 0;
    int mid2 = 0;
    // 每个数组至少两个数
    while (s1 < e1) {
        mid1 = (s1 + e1) >> 1;
        mid2 = (s2 + e2) >> 1;
        if (A[mid1] == B[mid2]) {
            return A[mid1];
        }
        if (((e1 - s1 + 1) & 1) == 0) { // 偶数长度
            // A： 1,   2,   3,  4,
            // B： 1‘,  2',  3', 4'
            // 上面的数字是代表编号（第几个数）
            // 上中位数就是第4位数
            if (A[mid1] > B[mid2]) { // 2, 3, 0', 1'排除
                e1 = mid1;
                s2 = mid2 + 1;
            } else { //反之
                e2 = mid2;
                s1 = mid1 + 1;
            }
        } else { // 奇数长度
            // A： 1,   2,   3,  4,  5
            // B： 1‘,  2',  3', 4', 5'
            // 上面的数字是代表编号（第几个数）
            // 上中位数就是第5位数
            if (A[mid1] > B[mid2]) {  // 2, 3, 4, 0', 1'排除
                if (B[mid2] >= A[mid1 - 1]) { // 手动抠一个， 若成立则找到了答案，返回
                    return B[mid2];
                }
                //不成立的话，那我们的迭代潜台词（两个数组等长）就可以维持下去了
                e1 = mid1 - 1;
                s2 = mid2 + 1;
            } else { //反之
                if (A[mid1] >= B[mid2 - 1]) {
                    return A[mid1];
                }
                e2 = mid2 - 1;
                s1 = mid1 + 1;
            }
        }
    }
    // 此时退出了while循环，此刻条件s1 == e1, while循环里面没找到答案
    // 说明每个数组此刻只剩一个数
    // 那么上中位数就返回其中比较小的一个即可
    return Math.min(A[s1], B[s2]);
}

```

时间复杂度

image.png