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

前言

最近在家闲着无聊看爱情公寓5，看上瘾了发现两天没刷题了，不好，所以去leetcode看了一下，找到一道比较有意思的题目（寻找两个有序数组的中位数），尝试做了一下，暴力解法还是挺简单的，二分法也比较有意思。所以来试着讲解一下（哈哈哈）

题目描述

暴力思路

先申请一个长度为nums1.length+nums2.length的辅助数组，然后利用归并排序的合并算法将两个数组合并成一个数组，并且是有序的数组。若长度为奇数，则中位数就是数组长度/2；若长度为偶数，则中位数就是数组长度/2和数组长度/2 - 1之和除以2。

代码

package leetcode;

/**
 * @author god-jiang
 * @date 2020/2/2  10:19
 */
public class FindMedianSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int length1 = nums1.length;
        int length2 = nums2.length;
        //申请一个长度为length1+length2的辅助数组res
        int[] res = new int[length1 + length2];
        int p1 = 0;
        int p2 = 0;
        int p = 0;
        //利用归并排序的merge操作进行两个数组合并，并且合并后的数组有序
        while (p1 < nums1.length && p2 < nums2.length) {
            if (nums1[p1] < nums2[p2]) {
                res[p++] = nums1[p1++];
            } else {
                res[p++] = nums2[p2++];
            }
        }
        while (p1 < nums1.length) {
            res[p++] = nums1[p1++];
        }
        while (p2 < nums2.length) {
            res[p++] = nums2[p2++];
        }

        if ((res.length & 1) == 1) {
            //合并后的数组长度为奇数
            return res[(res.length) / 2] / 1.0;
        } else {
            //为偶数
            return (res[(res.length) / 2 - 1] + res[(res.length) / 2]) / 2.0;
        }
    }
}

通过截图

复杂度分析

• 时间复杂度：O(M+N)，M是第一个数组的长度，N是第二个数组的长度
• 空间复杂度：O(M+N)，因为申请了一个辅助数组长度为M+N

---

二分解法代码（加注释）

package leetcode;

/**
 * @author god-jiang
 * @date 2020/2/2  10:59
 */
public class FindMedianSortedArrays {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        /*
         * 1.首先，让我们在任一位置 i 将 A(长度为m) 划分成两个部分：
         *            leftA            |                rightA
         *   A[0],A[1],...      A[i-1] |  A[i],A[i+1],...A[m - 1]
         *
         * 由于A有m个元素，所以有m + 1中划分方式(i = 0 ~ m)
         *
         * 我们知道len(leftA) = i, len(rightA) = m - i;
         * 注意：当i = 0时，leftA是空集，而当i = m时，rightA为空集。
         *
         * 2.采用同样的方式，将B也划分为两部分：
         *            leftB            |                rightB
         *   B[0],B[1],...      B[j-1] |   B[j],B[j+1],...B[n - 1]
         *  我们知道len(leftA) = j, len(rightA) = n - j;
         *
         *  将leftA和leftB放入一个集合，将rightA和rightB放入一个集合。再把这两个集合分别命名为leftPart和rightPart。
         *
         *            leftPart         |                rightPart
         *   A[0],A[1],...      A[i-1] |  A[i],A[i+1],...A[m - 1]
         *   B[0],B[1],...      B[j-1] |  B[j],B[j+1],...B[n - 1]
         *
         *   如果我们可以确认：
         *   1.len(leftPart) = len(rightPart); =====> 该条件在m+n为奇数时，该推理不成立
         *   2.max(leftPart) <= min(rightPart);
         *
         *   median = (max(leftPart) + min(rightPart)) / 2;  目标结果
         *
         *   要确保这两个条件满足：
         *   1.i + j = m - i + n - j(或m - i + n - j + 1)  如果n >= m。只需要使i = 0 ~ m，j = (m+n+1)/2-i =====> 该条件在m+n为奇数/偶数时，该推理都成立
         *   2.B[j] >= A[i-1] 并且 A[i] >= B[j-1]
         *
         *   注意:
         *   1.临界条件：i=0,j=0,i=m,j=n。需要考虑
         *   2.为什么n >= m ? 由于0 <= i <= m且j = (m+n+1)/2-i,必须确保j不能为负数。
         *
         *   按照以下步骤进行二叉树搜索
         *   1.设imin = 0,imax = m，然后开始在[imin,imax]中进行搜索
         *   2.令i = (imin+imax) / 2, j = (m+n+1)/2-i
         *   3.现在我们有len(leftPart) = len(rightPart)。而我们只会遇到三种情况：
         *
         *      ①.B[j] >= A[i-1] 并且 A[i] >= B[j-1]  满足条件
         *      ②.B[j-1] > A[i]。此时应该把i增大。 即imin = i + 1;
         *      ③.A[i-1] > B[j]。此时应该把i减小。 即imax = i - 1;
         *
         * */
        int m = nums1.length;
        int n = nums2.length;
        if (m > n) { // to ensure m<=n
            int[] temp = nums1;
            nums1 = nums2;
            nums2 = 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 && nums2[j - 1] > nums1[i]) {
                iMin = i + 1; // i is too small
            } else if (i > iMin && nums1[i - 1] > nums2[j]) {
                iMax = i - 1; // i is too big
            } else { // i is perfect
                int maxLeft;
                if (i == 0) {//A分成的leftA(空集) 和 rightA(A的全部)  所以leftPart = leftA(空集) + leftB,故maxLeft = B[j-1]。
                    maxLeft = nums2[j - 1];
                } else if (j == 0) { //B分成的leftB(空集) 和 rightB(B的全部)  所以leftPart = leftA + leftB(空集),故maxLeft = A[i-1]。
                    maxLeft = nums1[i - 1];
                } else { //排除上述两种特殊情况，正常比较
                    maxLeft = Math.max(nums1[i - 1], nums2[j - 1]);
                }
                if ((m + n) % 2 == 1) { //奇数，中位数正好是maxLeft
                    return maxLeft;
                }
                //偶数
                int minRight;
                if (i == m) {//A分成的leftA(A的全部) 和 rightA(空集)  所以rightPart = rightA(空集) + rightB,故minRight = B[j]。
                    minRight = nums2[j];
                } else if (j == n) {//B分成的leftB(B的全部) 和 rightB(空集)  所以rightPart = rightA + rightB(空集),故minRight = A[i]。
                    minRight = nums1[i];
                } else {//排除上述两种特殊情况，正常比较
                    minRight = Math.min(nums2[j], nums1[i]);
                }

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

}

通过截图

复杂度分析

• 时间复杂度：O(log(M,N))
• 空间复杂度：O(1)

PS：该解法参考leetcode上的官方解法加上一些注释。