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

by: dick 林敏悦 2020-08-04

保护私人版权，尊重他人版权。转载请注明出处并附带页面链接

一、题目

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

题目描述：给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

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

你可以假设 nums1 和 nums2 不会同时为空。

二、思路

简单思路：排序合并成一个大数组，类似归并排序的操作，然后求中位数即可。

时间复杂度O（m + n)，空间复杂度O（m + n）。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int[] newArr = new int[nums1.length + nums2.length];

    int m = 0, i = 0, j = 0;
    while(i < nums1.length && j < nums2.length) {
        newArr[m++] = nums1[i] < nums2[j] ? nums1[i++] : nums2[j++];
    }

    while(i < nums1.length) {
        newArr[m++] = nums1[i++];
    }

    while(j < nums2.length) {
        newArr[m++] = nums2[j++];
    }

    if(newArr.length % 2 == 1) {
        return (double)newArr[newArr.length/2];
    } else {
        return (newArr[newArr.length/2 - 1] + newArr[newArr.length/2])/2.0;
    }
}

双指针法：类似归并的操作，只是不合成数组，用指针跑即可。

时间复杂度O(m + n)，实际时间复杂度只有O（m + n + 1) / 2），空间复杂度O（1）。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    int m = nums1.length;
    int n = nums2.length;
    //这里也可以处理一下溢出totalL = m + (n - m + 1) / 2
    int totalL = (m + n + 1) / 2;

    int p1 = 0;
    int p2 = 0;
    while (p1 < m && p2 < n && p1 + p2 < totalL) {
        if (nums1[p1] > nums2[p2]) {
            p2++;
        } else {
            p1++;
        }
    }

    while (p1 < m && p1 + p2 < totalL) {
        p1++;
    }

    while (p2 < n && p1 + p2 < totalL) {
        p2++;
    }

    int maxLeft1 = p1 == 0 ? Integer.MIN_VALUE : nums1[p1 - 1];
    int maxLeft2 = p2 == 0 ? Integer.MIN_VALUE : nums2[p2 - 1];
    int maxRight1 = p1 == m ? Integer.MAX_VALUE : nums1[p1];
    int maxRight2 = p2 == n ? Integer.MAX_VALUE : nums2[p2];

    //分配律处理溢出 (m + n) % 2 = m % 2 + n % 2
    if (m % 2 + n % 2 == 1) {
        return Math.max(maxLeft1, maxLeft2);
    } else {
        return (double) (Math.max(maxLeft1, maxLeft2) + Math.min(maxRight1, maxRight2)) / 2;
    }
}

二分法：用分割线的思路，对于两个数组求中位数，其实就是在找一个中间分割点使得分割点左边的元素与右边元素大致相等（大致是因为数量的奇偶）。根据这个思路，我们尝试对两个数组分别切一刀，使得

1	数组1的左边个数 + 数组2的左边个数 ~= 数组1的右边个数 + 数组2的右边个数。

考虑到对数组1切的一刀已经能够确定一刀后左右两边剩下的个数了，即能够推出数组2的一刀应该在哪里。假设数组1的长度为m，数组2的长度为n，那么左右两边的个数大致相等的情况下，个数应该为(m+n+1)/2，如果数组1的一刀落在i位置，数组2的一刀落在j位置，j应该满足：

1	j = (m + n + 1) / 2 - i;

如此一来，我们便可以在数组1中进行二分查找，然后根据数量关系在数组2切第二刀，比较两刀左右元素的大小关系来调整二分的缩小方向，最终得到答案。

时间复杂度O(log(min(m,n)))，m为nums1的长度，n为nums2的长度。空间复杂度O（1）。

public double findMedianSortedArrays(int[] nums1, int[] nums2) {
    //这样可以得到O(log(min(m,n)))的复杂度，因为我们只二分第一个数组
    if (nums1.length > nums2.length) {
        return findMedianSortedArrays(nums2, nums1);
    }

    int m = nums1.length;
    int n = nums2.length;
    //这里也可以处理一下溢出totalL = m + (n - m + 1) / 2
    int totalL = (m + n + 1) / 2;

    int l = 0;
    int r = nums1.length - 1;

    while (l <= r) {
        int i = l + (r - l) / 2;
        int j = totalL - i;
        /*
        满足的条件是 nums1[i] >= nums2[j - 1] && nums1[i - 1] <= nums2[j]
        取反就是 nums1[i] < nums2[j - 1] || nums2[i - 1] > nums1[j]，取其中一个条件即可
        考虑题目条件：两个数组不会同时为空，而且前面已经处理成nums1.length <= nums2.length，i - 1有越界风险，采用nums1[i] < nums2[j - 1]
        */
        if (nums1[i] < nums2[j - 1]) {
            l = i + 1;
        } else {
            r = i - 1;
        }
    }

    int i = l;
    int j = totalL - i;

    //处理切割点落在数组头尾的情况
    int maxLeft1 = i == 0 ? Integer.MIN_VALUE : nums1[i - 1];
    int maxLeft2 = j == 0 ? Integer.MIN_VALUE : nums2[j - 1];
    int maxRight1 = i == m ? Integer.MAX_VALUE : nums1[i];
    int maxRight2 = j == n ? Integer.MAX_VALUE : nums2[j];
    //分配律处理溢出 (m + n) % 2 = m % 2 + n % 2
    if (m % 2 + n % 2 == 1) {
        return Math.max(maxLeft1, maxLeft2);
    } else {
        return (double) (Math.max(maxLeft1, maxLeft2) + Math.min(maxRight1, maxRight2)) / 2;
    }
}