寻找两个正序数组中的中位数 - Grey Zeng

作者：Grey

原文地址：寻找两个正序数组中的中位数

LeetCode 4. 寻找两个正序数组中的中位数

例如：nums1数组是 [1,2], nums2 数组是 [3,4]
那么这两个数组的合并数组是[1,2,3,4] ，所以中位数 (2 + 3) / 2 = 2.5

再比如：nums1数组是 [1,2,3], nums2 数组是 [4,5]
那么这两个数组的合并数组是[1,2,3,4,5] ，所以中位数 3

时间和空间都是O(M+N)的解法

这不是最优解，但是是最容易想到的一个解法，即，创建一个合并数组，这个数据的长度就是两个数据长度之和，然后通过合并有序数组的方法将这个合并数组生成出来，如果合并数组长度是奇数，则取中间值，如果合并长度是偶数，则取上中位数和下中位数，通过（上中位数+下中位数）/ 2 得到结果。

这个解法的时间复杂度和空间复杂度都是O(M+N), 比较简单，完整代码如下：

public double findMedianSortedArrays1(int[] nums1, int[] nums2) {
        // 题目已经说明nums1和nums2不能同时为空
        if (null == nums1 || nums1.length == 0) {
            return median(nums2);
        }
        if (null == nums2 || nums2.length == 0) {
            return median(nums1);
        }
        int m = nums1.length;
        int n = nums2.length;
        int[] nums = new int[m + n];
        int i = 0;
        int j = 0;
        int index = 0;
  // 合并两个有序数组的实现
        while (i < m && j < n) {
            if (nums1[i] >= nums2[j]) {
                nums[index++] = nums2[j++];
            } else {
                nums[index++] = nums1[i++];
            }
        }
        while (i < m) {
            nums[index++] = nums1[i++];
        }
        while (j < n) {
            nums[index++] = nums2[j++];
        }
        return median(nums);
    }
    // 求一个有序数组的中位数
    // 如果是奇数，直接返回中间位置的值
    // 如果是偶数，则返回（上中位数+下中位数）/ 2的值
    public static double median(int[] arr) {
        int len = arr.length;
        if ((len & 1) == 1) {
            // 奇数
            return arr[len / 2];
        }
        return ((arr[len / 2] + arr[(len - 1) / 2]) / 2d);
    }

时间复杂度O(log(M+N))的解法

如果我们可以高效实现如下方法：

// 在O(log(M+N))时间复杂度下找到num1和num2这两个有序数组合并后的第k大的数是什么
int findKth(int[] nums1, int[] nums2, int k)

那么题目就可以通过如下方式实现：

   public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 题目已经说明nums1和nums2不能同时为空
        if (null == nums1 || nums1.length == 0) {
            return median(nums2);
        }
        if (null == nums2 || nums2.length == 0) {
            return median(nums1);
        }
        int m = nums1.length;
        int n = nums2.length;
			
        if (((m + n) & 1) == 1) {
           // 合并后的数组长度是奇数，则取中间这个数
            return findKth(nums1, nums2, (m + n) / 2 + 1);
        }
        // 合并后的数组长度如果是偶数，则返回（上中位数+下中位数）/ 2的值
        return (findKth(nums1, nums2, (m + n) / 2) + findKth(nums1, nums2, ((m + n) / 2 + 1))) / 2d;
    }

现在所有的目光都聚焦在这个算法中，

// 在O(log(M+N))时间复杂度下找到num1和num2这两个有序数组合并后的第k大的数是什么
int findKth(int[] nums1, int[] nums2, int k)

注：以上算法中，我们规定k以1开始计算，也就是说：合并数组中最小的数是第1小的，而不是第0小的。且在调用的时候，保证1<= k <= nums1.lengh + nums2.length。

在解决这个算法之前，假设我们已经有一个方法，可以高效得到：两个长度相等的排序数组合并后的上中位数，我们假设这个方法为：

// 获取两个长度相等的有序数组merge后的上中位数
// 如果是偶数，取上中位数
// 调用该方法的时候保证[s1...e1] 和 [s2...e2]等长
int getUpMedian(int[] A, int s1, int e1, int[] B, int s2, int e2) 

一旦我们有getUpMedian这个方法，我们就可以针对k的取值，分多种情况来解决findKth方法，我们假设

int findKth(int[] nums1, int[] nums2, int k)

方法中，较长的数组我们重新定义为名字为longs的数组，较短的数组重新定义为名字shorts的数组。

现在开始讨论k的范围：

第一种情况：k<=shorts.length

在这种情况下比较简单，我们可以将longs数组取前k个数，shorts数组取前k个数，然后调用getMedian方法，拿到中位数，即是longs和shorts数组合并后的第k小的数。

例如：shorts数组为[1,3,5,7]，longs数组为[2,4,6,8,10,12]
如果要取第2小的数, 客观上第2小的数是2，可能存在的范围是shorts的前2个数中，也可能存在在longs的前2个数中，除此之外，不能是其他范围，因为超过这个范围，就不止第2小了。

第二种情况：shorts.length<k<=longs.length

在这种情况下，shorts数组中的每个数都有可能，longs数组可以排除掉 前(k - shorts.len - 1) 个数，以及[kth + 1......longs.length]区间的所有数，但是要手动验证一下long中第(k- shorts.len)位置上的数是不是比shorts最后一个数大，
如果是，longs中第(k - shorts.length)位置上的数即为第k小的数,
如果不是，longs中第(k - shorts.length)位置上的数直接排除掉,
longs中剩余数和shorts中所有数用一次getUpMedian方法求得的值即为第k小的数。

例如：shorts数组为[1,3,5,7]，longs数组为[2,4,6,8,10,12,14,16,18]
求第7小的数，此时shorts中的数都有可能是第7小的数，但是，longs中，可以排除如下位置的数

首先：从第8小的数开始一直到第longs.length小的数都可以排除。

其次， 7 - shorts.length - 1 即：7 - 4 - 1 = 3 ，longs中第3小之前的数都可以排除，

排除完毕后，验证一下longs中第3小的数是不是比shorts中最后一个数大，如果是，则longs中第3小的数即位两个数组的第7小的数。

如果不是，则longs中剩余可选的数继续和shorts调用getUpMedian方法。

第三种情况：longs.length<=k<=(shorts.length+longs.length)

这种情况下，shorts中可排除掉前面(k - longs.length)个数，longs中排除掉前( k - shorts.length - 1) 个数，然后手动判断下shorts和longs中剩余数中最左边的数是不是第k小的数，如果是，直接返回，如果不是，排除掉这些数，然后将shorts和longs剩余数用getUpMedian获取的结果即为答案。
例如：shorts数组为 [1,3,5,7,9,11] 长度是6，longs数组为 [2,4,6,8,10,12,14,16,18,20,22,24] 长度是12，假设要求第15小的数，那么在shorts中可以排除掉前面（15 - longs.length - 1）= 2个数， 因为即便shorts中第1小的数比longs中所有数都大，它也只能算第13小的数，第2小的数即便比longs中所有数都大，也只能算全局第14小的数。longs中可以排除掉第1一直到第8小（即：15 - shorts.length - 1 = 8）的数，因为longs中第8小的数即便比shorts数所有数都大，也只能是全局第14小的数。经过排除后，shorts中和longs中可选范围为（以下数组中没打x的数字）

shorts中为[x,x,5,7,9,11]

longs中为[x,x,x,x,x,x,x,x,18,20,22,24]

先手动判断一下，longs中的18和shorts中的5是否是第15小的数，如果是则直接返回，如果不是，shorts中[7,9,11] 和 longs中 [20,22,24] 使用getUpMedian获取的结果即为答案。

所有情况说明完毕，而且三种情况仅依赖getUpMedian 方法。所以，现在看getUpMedian 方法的实现，具体说明见注释：

// 获取两个长度相等的有序数组merge后的上中位数
// 如果是偶数，取上中位数
// 调用该方法的时候保证[s1...e1] 和 [s2...e2]等长
    public static int getUpMedian(int[] A, int s1, int e1, int[] B, int s2, int e2) {
        if (s1 == e1) {
          // 说明A和B分别只有一个数，因为求上中位数，所以取A[s1]和B[s2]的最小值
            return Math.min(A[s1], B[s2]);
        }
        int mid1 = (s1 + e1) / 2;
        int mid2 = (s2 + e2) / 2;
      // 如果A和B的中位数值一样，则这个中位数值也是A和B合并后的中位数值
        if (A[mid1] == B[mid2]) {
            return A[mid1];
        }
        boolean even = ((e1 - s1) & 1) != 0; // 是否是偶数
        if (even) {
          // 通过类似二分的方式，判断A和B的中位数可能出现的位置，
            if (A[mid1] > B[mid2]) {
               // 如果A[mid1] > B[mid2]
              // 则全局的中位数只可能在A的[s1..mid1]以及B的[mid2+1..e2]范围内产生
              // 下面的判断类似。
                return getUpMedian(A, s1, mid1, B, mid2 + 1, e2);
            } else {
                return getUpMedian(A, mid1 + 1, e1, B, s2, mid2);
            }
        } else {
            if (A[mid1] > B[mid2]) {
                if (B[mid2] > A[mid1 - 1]) {
                    return B[mid2];
                }
                return getUpMedian(A, s1, mid1 - 1, B, mid2 + 1, e2);
            } else {
                if (A[mid1] > B[mid2 - 1]) {
                    return A[mid1];
                }
                return getUpMedian(A, mid1 + 1, e1, B, s2, mid2 - 1);
            }
        }
    }

getUpMedian通过类似二分查找的方法，来得到中位数信息，复杂度就是O(log(M+N))。完整代码见：

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 题目已经说明nums1和nums2不能同时为空
        if (null == nums1 || nums1.length == 0) {
            return median(nums2);
        }
        if (null == nums2 || nums2.length == 0) {
            return median(nums1);
        }
        int m = nums1.length;
        int n = nums2.length;

        if (((m + n) & 1) == 1) {
            return findKth(nums1, nums2, (m + n) / 2 + 1);
        }
        return (findKth(nums1, nums2, (m + n) / 2) + findKth(nums1, nums2, ((m + n) / 2 + 1))) / 2d;
    }
    public static double median(int[] arr) {
        int len = arr.length;
        if ((len & 1) == 1) {
            // 奇数
            return arr[len / 2];
        }
        return ((arr[len / 2] + arr[(len - 1) / 2]) / 2d);
    }
   
    public static int findKth(int[] nums1, int[] nums2, int k) {
        int[] longs = nums1.length > nums2.length ? nums1 : nums2;
        int[] shorts = nums1 == longs ? nums2 : nums1;
        int maxLen = longs.length;
        int minLen = shorts.length;
        // k<= minLen
        // longs截取前k个数，shorts截取前k个数，两个长度相等的数组取上中位数
        if (k <= minLen) {
            return getUpMedian(shorts, 0, k - 1, longs, 0, k - 1);
        }
        // k > minLen 且 k <= maxLen
        // 到这里一定k > minLen
        if (k <= maxLen) {
            // 可以排除
            // longs中比第k小的数还大的所有数都可以排除，即下标为：[k....maxLen - 1]
            // longs中第1小到第(k - minLen - 1)小的数都可以排除
            // shorts中所有数都有可能

            // 手动验证
            // longs中第 (k - minLen) 大的数是否比shorts中最后一个数大，如果是，这个数直接就是结果
            if (longs[k - minLen - 1] >= shorts[minLen - 1]) {
                return longs[k - minLen - 1];
            }
            // 其他的数
            return getUpMedian(shorts, 0, minLen - 1, longs, k - minLen, k - 1);
        }
        // k > maxLen 且 k <= maxLen + minLen
        // 到这里一定 k > maxLen 且 k <= maxLen + minLen
      
      
        // 可以排除
        // shorts中从第1小一直到第k - maxLen - 1小的数都可以排除
        // longs中第1小的数一直到第k - minLen - 1小的数都可以排除

        // 手动验证
        if (shorts[minLen - 1] <= longs[k - minLen - 1]) {
            return longs[k - minLen - 1];
        }
        if (longs[maxLen - 1] <= shorts[k - maxLen - 1]) {
            return shorts[k - maxLen - 1];
        }
        // 其他的数
        return getUpMedian(shorts, k - maxLen, minLen - 1, longs, k - minLen, maxLen - 1);
    }

    public static int getUpMedian(int[] A, int s1, int e1, int[] B, int s2, int e2) {
        if (s1 == e1) {
            return Math.min(A[s1], B[s2]);
        }
        int mid1 = (s1 + e1) / 2;
        int mid2 = (s2 + e2) / 2;
        if (A[mid1] == B[mid2]) {
            return A[mid1];
        }
        boolean even = ((e1 - s1) & 1) != 0; // 是否是偶数
        if (even) {
            if (A[mid1] > B[mid2]) {
                return getUpMedian(A, s1, mid1, B, mid2 + 1, e2);
            } else {
                return getUpMedian(A, mid1 + 1, e1, B, s2, mid2);
            }
        } else {
            if (A[mid1] > B[mid2]) {
                if (B[mid2] > A[mid1 - 1]) {
                    return B[mid2];
                }
                return getUpMedian(A, s1, mid1 - 1, B, mid2 + 1, e2);
            } else {
                if (A[mid1] > B[mid2 - 1]) {
                    return A[mid1];
                }
                return getUpMedian(A, mid1 + 1, e1, B, s2, mid2 - 1);
            }
        }
    }
}

算法和数据结构笔记