Leetcode-计算两个排序数组的中位数

题目描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2 。

请找出这两个有序数组的中位数。要求算法的时间复杂度为 O(log (m+n)) 。

示例 1:

示例 2:

算法实现

我的实现思路

• 根据元素总个数，计算出中位数的位置。
  • 如果总个数为奇数，则中位数取中间一个即可。
  • 如果总个数为偶数，则需要取中间两个数之和的平均值。
• 假设桌上有两副已排好序的扑克牌，从上到下由小到大排序。那么
  • 从两副牌的顶部各取一张，进行比较后取最小的一张牌。
  • 从取出最小牌的那副再取一张，与另一副前一次抽取的牌进行比较，然后取最小的一张牌。
  • 如此循环，我们拿到的牌将是从小到大的顺序，直至拿到牌的数量与我们要找的中位数位置相同即可停止。
  • 此时，如果判断元素总数为偶数个，则再取一张牌后停止。
• 最后，如果是奇数个元素，则直接返回。如果是偶数个元素，则返回两个数之和的平均值。

/**
 * 个人实现版本.
 * 
 * @param nums1
 * @param nums2
 * @return
 */
public static double findMedianSortedArraysV1(int[] nums1, int[] nums2) {
    int[] resultArray = new int[2];
    int idx1 = 0;
    int idx2 = 0;
    int currentCount = 0;

    int size1 = (nums1 == null) ? 0 : nums1.length;
    int size2 = (nums2 == null) ? 0 : nums2.length;

    boolean evenResult = true; // 总数是否为偶数个
    int medianNum = (size1 + size2) / 2; // 中位数的位置
    if ((size1 + size2) % 2 != 0) {
        medianNum++;
        evenResult = false; // 总数为奇数个
    }
    if (medianNum == 0) {
        throw new IllegalArgumentException("median num not found");
    }

    int currentValue = 0;
    while (true) {
        if (idx1 <= size1 - 1 && idx2 <= size2 - 1) {
            if (nums1[idx1] <= nums2[idx2]) {
                currentValue = nums1[idx1++];
            } else {
                currentValue = nums2[idx2++];
            }
            currentCount++;
        } else if (idx1 <= size1 - 1) {
            currentValue = nums1[idx1++];
            currentCount++;
        } else if (idx2 <= size2 - 1) {
            currentValue = nums2[idx2++];
            currentCount++;
        }

        // 相等则找到中位数
        if (currentCount == medianNum) {
            resultArray[0] = currentValue;
            if (!evenResult) { // 如果总数为偶数，需要找到中间的2个数取平均值
                break;
            }
        } else if (currentCount > medianNum && evenResult) { // 找到第二数
            resultArray[1] = currentValue;
            break;
        }
    }

    double resultValue = evenResult ? Double.valueOf(resultArray[0] + resultArray[1]) / 2 : Double.valueOf(resultArray[0]);

    return resultValue;
}

个人实现的版本，时间复杂度为O((m+n)/2)，比题目的要求慢一些，不过思路相对清晰一些。

习题答案

个人理解如下：

假设有数组A，长度为m，任意位置i将数组分为左右两部分。数组B，长度为n，任意位置j将数组分为左右两部分。

那么i>=0，且i<=m。j>=0，且j<=n。i和j可以理解为数组从小到大的第几个数，例如i=1代表A[0]，即数组A的第一个数。

如果要找到A和B各自的中位数，需要满足i=m-i，j=n-j，即左右两部分的个数是相同的，此时中间的数即为中位数。当然，实现的时候仍需要考虑奇数、偶数个数组元素的问题。

由于我们是在A和B两个数组合并之后找中位数，因此找到中位数需要满足i+j=m-i+n-j（或：m-i+n-j+1，奇数个元素的情况）。

另外，题目要求的时间复杂度是log(m+n)，所以很容易想到二分查找（如折半查找、二叉查找树）。所以问题的关键点就是，在不合并数组并做好排序（时间复杂度为O(m)、O(n)或O(m+n)，肯定不满足需求）的情况下，如何利用二分查找来实现该算法。

由前面我们推导出的公式可知，j=(m+n)/2-i或j=(m+n+1)/2-i。

事实上，如果要简单的理解可以不用这么麻烦的推导。

假设数组元素的总个数为奇数，那么中位数必然在第(m + n + 1) / 2个。

此时，要找到中位数，显然i+j=(m + n + 1) / 2，这个结果与上述的推导是一致的。有了这个公式，二分查找就好办了。分而治之，先计算出数组A的中间位置i=(0+m)/2。那么，此时j就可以通过前面的公式计算出来了。

二分查找时，如果满足B[j−1]<=A[i]且A[i−1]<=B[j]，则表示找到中位数了，结束查找。如果不满足，则在i的前或后半部分继续进行上述的二分查找，直至满足条件即可。

为什么说满足B[j−1]<=A[i]且A[i−1]<=B[j]，则表示找到中位数了？

因为A[i−1]+B[j−1]代表数组的一半元素，共有i+j个。那么只要满足最后一个条件，我们就找到中位数了。最后一个条件，就是A[i−1]和B[j−1]都要小于等于另一半元素的值，这里我们只要保证同时小于另一半的最小值A[i]和B[j]（或者说是下一个值）即可。

/**
 * 习题答案
 * 
 * @param A
 * @param B
 * @return
 */
public double findMedianSortedArrays(int[] A, int[] B) {
    int m = A.length;
    int n = B.length;
    if (m > n) { // to ensure m<=n
        int[] temp = A; A = B; B = temp;
        int tmp = m; m = n; n = tmp;
    }
    int iMin = 0, iMax = m, halfLen = (m + n + 1) / 2;
    while (iMin <= iMax) {
        int i = (iMin + iMax) / 2;
        int j = halfLen - i;
        if (i < iMax && B[j-1] > A[i]){
            iMin = iMin + 1; // i is too small
        }
        else if (i > iMin && A[i-1] > B[j]) {
            iMax = iMax - 1; // i is too big
        }
        else { // i is perfect
            int maxLeft = 0;
            if (i == 0) { maxLeft = B[j-1]; }
            else if (j == 0) { maxLeft = A[i-1]; }
            else { maxLeft = Math.max(A[i-1], B[j-1]); }
            if ( (m + n) % 2 == 1 ) { return maxLeft; }

            int minRight = 0;
            if (i == m) { minRight = B[j]; }
            else if (j == n) { minRight = A[i]; }
            else { minRight = Math.min(B[j], A[i]); }

            return (maxLeft + minRight) / 2.0;
        }
    }
    return 0.0;
}

算法实现

https://github.com/qiuzj/leetcode/blob/master/src/main/java/cn/javaee/leetcode/q4/median_of_two_sorted_arrays/MedianOfTwoSortedArrays.java

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

转载请注明来源：http://zhanjia.iteye.com/blog/2427289

个人公众号

二进制之路