寻找两个正序数组的中位数

给定两个大小分别为 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[i], nums2[i] <= 106

算法原型一：

假设我们有一个int get(arr1,arr2,int k)函数。arr1有序，arr2有序，可以返回第k大的数。

那求两个正序数组的中位数，我们就可以借助get来完成

• 假设arr1.length+arr2.length= 奇数

image-20210420092701662

• 假设arr1.length+arr2.length=偶数

image-20210420092855942

如果我们把int get(arr1,arr2,int k)这个函数实现了的话，本题就通过调用get来完成，求两个有序数组的中位数。

为了实现算法原型一，我们需要另外一个f(arr1,arr2)来辅助，要求，arr1和arr2 长度一致且有序，返回上中位数。

image-20210420094239125

public static int getUpMedian(int[] A, int s1, int e1, int[] B, int s2, int e2)

• 函数要求输入参数 e1-s1==e2-s2 两断一定等长

• 两断等长的数组一定有序

返回值：两段整体的上中位数(上中位数值返回)

// 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) / 2;
      mid2 = (s2 + e2) / 2;
      if (A[mid1] == B[mid2]) {
         return A[mid1];
      }
      if (((e1 - s1 + 1) & 1) == 1) { // 奇数长度
         if (A[mid1] > B[mid2]) {
            if (B[mid2] >= A[mid1 - 1]) {
               return B[mid2];
            }
            e1 = mid1 - 1;
            s2 = mid2 + 1;
         } else { // A[mid1] < B[mid2]
            if (A[mid1] >= B[mid2 - 1]) {
               return A[mid1];
            }
            e2 = mid2 - 1;
            s1 = mid1 + 1;
         }
      } else { // 偶数长度
         if (A[mid1] > B[mid2]) {
            e1 = mid1;
            s2 = mid2 + 1;
         } else {
            e2 = mid2;
            s1 = mid1 + 1;
         }
      }
   }
   return Math.min(A[s1], B[s2]);
}

arr1和arr2数偶数

image-20210420101137816

• 2==B

image-20210420095638778

• 2>B

image-20210420101129138

image-20210420101434941

image-20210420101814245

arr1和arr2数奇数

image-20210420102329443

3==c return 3

3>c

image-20210420103804109

Arr1[]=[1,2] arr2[3,4,5] ，不等长了，无法递归调用getUpMedian现在怎么办？？？

image-20210420104652576

public static int findKthNum(int[] arr1, int[] arr2, int kth)

arr1 arr2有序，求第Kth小的数

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(shorts, 0, kth - 1, longs, 0, kth - 1);
   }
   if (kth > l) {
      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);
   }
   if (longs[kth - s - 1] >= shorts[s - 1]) {
      return longs[kth - s - 1];
   }
   return getUpMedian(shorts, 0, s - 1, longs, kth - s, kth - 1);
}

第一种情况 kth <= s

image-20210420110200488

第二种情况 kth大于短数组长度，小于长数组长度。

image-20210420111233999

image-20210420112035289

第三种情况 kth大于长数组长度，小于等于两个数组长度之和。

image-20210420113004754

image-20210420114523972

class Solution {
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int size = nums1.length + nums2.length;
        boolean even = (size & 1) == 0;
        if (nums1.length != 0 && nums2.length != 0) {
            if (even) {
                return (double) (findKthNum(nums1, nums2, size / 2) + findKthNum(nums1, nums2, size / 2 + 1)) / 2D;
            } else {
                return findKthNum(nums1, nums2, size / 2 + 1);
            }
        } else if (nums1.length != 0) {
            if (even) {
                return (double) (nums1[(size - 1) / 2] + nums1[size / 2]) / 2;
            } else {
                return nums1[size / 2];
            }
        } else if (nums2.length != 0) {
            if (even) {
                return (double) (nums2[(size - 1) / 2] + nums2[size / 2]) / 2;
            } else {
                return nums2[size / 2];
            }
        } else {
            return 0;
        }
    }

    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(shorts, 0, kth - 1, longs, 0, kth - 1);
        }
        if (kth > l) {
            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);
        }
        if (longs[kth - s - 1] >= shorts[s - 1]) {
            return longs[kth - s - 1];
        }
        return getUpMedian(shorts, 0, s - 1, longs, kth - s, kth - 1);
    }

    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) / 2;
            mid2 = (s2 + e2) / 2;
            if (A[mid1] == B[mid2]) {
                return A[mid1];
            }
            if (((e1 - s1 + 1) & 1) == 1) { // 奇数长度
                if (A[mid1] > B[mid2]) {
                    if (B[mid2] >= A[mid1 - 1]) {
                        return B[mid2];
                    }
                    e1 = mid1 - 1;
                    s2 = mid2 + 1;
                } else { // A[mid1] < B[mid2]
                    if (A[mid1] >= B[mid2 - 1]) {
                        return A[mid1];
                    }
                    e2 = mid2 - 1;
                    s1 = mid1 + 1;
                }
            } else { // 偶数长度
                if (A[mid1] > B[mid2]) {
                    e1 = mid1;
                    s2 = mid2 + 1;
                } else {
                    e2 = mid2;
                    s1 = mid1 + 1;
                }
            }
        }
        return Math.min(A[s1], B[s2]);
    }
}

image-20210420114850979

其他优秀解法

https://www.youtube.com/watch?v=LPFhl65R7ww&ab_channel=TusharRoy-CodingMadeSimple

    public double findMedianSortedArrays(int[] nums1, int[] nums2) {

        if (nums1.length > nums2.length) {
            return findMedianSortedArrays(nums2, nums1);
        }

        int startX = 0;
        int endX = nums1.length;

        boolean cont = true;

        double median = 0;
        int firstHalfSize = (nums1.length + nums2.length + 1) / 2;
        while (cont) {
            int partitionX = (startX + endX) / 2;
            int partitionY = firstHalfSize - partitionX;
            int xFirstHalfMax = partitionX == 0 ? Integer.MIN_VALUE : nums1[partitionX - 1];
            int xSecondHalfMin = partitionX == nums1.length ? Integer.MAX_VALUE : nums1[partitionX];

            int yFirstHalfMax = partitionY == 0 ? Integer.MIN_VALUE : nums2[partitionY - 1];
            int ySecondHalfMin = partitionY == nums2.length ? Integer.MAX_VALUE : nums2[partitionY];

            if (xFirstHalfMax <= ySecondHalfMin && yFirstHalfMax <= xSecondHalfMin) {
                if ((nums1.length + nums2.length) % 2 == 0) {
                    int medPart1 = Math.max(xFirstHalfMax, yFirstHalfMax);
                    int medPart2 = Math.min(xSecondHalfMin, ySecondHalfMin);
                    median = (medPart1 + medPart2) * 1.0 / 2;
                } else {
                    median = Math.max(xFirstHalfMax, yFirstHalfMax);
                }

                cont = false;
            } else if (xFirstHalfMax > ySecondHalfMin) {
                endX = partitionX - 1;
            } else {
                startX = partitionX + 1;
            }
        }

        return median;
    }

image-20210420115844543