题目

LeetCode.4.寻找两个正序数组的中位数（困难）

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。

进阶：你能设计一个时间复杂度为 O(log (m+n)) 的算法解决此问题吗？

题解

解法1: 归并

一个数组怎么找中位数？

数组元素有奇数个，中位数是最中间的一个数。
数组元素有偶数个，中位数是最中间的两个数的平均值。

设数组长度为n。

n为奇数时，中位数应该是第n / 2 + 1个数，由于数组索引从0开始，所以中位数是nums[n / 2]。
n为偶数时，左中位数是第n / 2个数，右中位数是第n / 2 + 1个数；由于数组索引从0开始，左中位数为nums[n / 2 - 1]，右中位数为nums[n / 2]，实际中位数为(nums[n / 2 - 1] + nums[n / 2]) / 2。

两个数组怎么找中位数？

把两个数组归并为一个有序数组。

复杂度

时间复杂度O(m + n)：需要遍历两个数组所有元素做归并。
空间复杂度O(m + n)：额外需要一个m + n长度的数组存储归并后的元素。

class Solution {
    fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
        val m = nums1.size
        val n = nums2.size

        // 二路归并
        val nums = IntArray(m + n) { 0 }
        var i1 = 0
        var i2 = 0
        var j = 0
        while (i1 < m && i2 < n) {
            nums[j++] = if (nums1[i1] < nums2[i2]) nums1[i1++] else nums2[i2++]            
        }
        while (i1 < m) nums[j++] = nums1[i1++]
        while (i2 < n) nums[j++] = nums2[i2++]

        // 取中位数
        return if ((m + n) % 2 == 1) {
            val mid = (m + n) / 2
            nums[mid].toDouble()
        } else {
            val leftMid = (m + n) / 2 - 1
            val rightMid = leftMid + 1
            (nums[leftMid] + nums[rightMid]).toDouble() / 2
        }
    }
}

解法2：二分

思路

归并排序产生了新数组，增加了空间复杂度。

既然在一个数组中找中位数不需要额外空间，两个数组应该也能。

我们的思路还是把两个数组往一个数组的情况上考虑，也就是把不熟悉的情况往熟悉的情况上靠拢。

合二为一

找中位数是跟数组总个数有关的，如果把小的元素和大的元素正好能各分一半，那么看中间的数就行。

可以把两个数组分割为左右两部分，两个数组的左半部分元素个数跟右半部分元素个数相等的时候，直接看中间的元素就行了。

设nums1数组长度为m，nums2数组长度为n。
把nums1分为前i个元素和后m - i个元素。
把nums2分为前j个元素和后n - j个元素。

如果m + n是偶数，i + j = (m + n) / 2。
如果m + n是奇数，i + j = (m + n) / 2 + 1。
知道了i就可以确定j。

怎么确定`i` ？

左半部分所有元素都小于右半部分的元素。

数组本身是有序的，所以要求两个数组的不同部分也保持顺序，即：
nums1[i - 1] < nums2[j] && nums2[j - 1] < nums1[i]

这个条件等价于在nums1数组中查找最大的i来满足nums1[i - 1] < nums2[j]，查找过程可以用二分查找。

二分查找的细节

当发现nums[i - 1] > nums2[j]，说明左半部分的元素多了，要减少，应当继续寻找更小的i。
当发现nums[i - 1] <= nums2[j]，说明左半部分可能正好，也可能少了，可以尝试寻找更大的i。

查找完毕后怎么确定中位数？

查找到最大的i过后，就可以选取中位数了。

如果m + n是奇数，分割数组的时候可以让左半部分多一个元素，两数组左半部分最大值即为中位数。
如果m + n是偶数，两数组左半部分最大值和右半部分最小值的平均数即为中位数。

复杂度

时间复杂度O(log(min(m, n)))，在短的数组里做了二分查找。
空间复杂度O(1)，只使用了常数个的辅助变量。

class Solution {
    fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
        val m = nums1.size
        val n = nums2.size
        if (m > n) return findMedianSortedArrays(nums2, nums1)

        val leftCount = if((m + n) % 2 == 0) (m + n) / 2 else (m + n) / 2 + 1

        var left = 0
        var right = m
        // 循环结束时left == right，不用思考选取left还是right
        while (left < right) {
            // 计算mid向上取整，否则最后只剩两个元素的时候，下面一直走到else，左边界不会更新
            val i = left + (right - left + 1) / 2
            val j = leftCount - i
            // i不满足条件，要找更小的
            if (nums1[i - 1] > nums2[j]) right = i - 1
            // i满足条件，i可能是要求解的结果，不要跳过i
            else left = i
        }
        val i = left
        val j = leftCount - left

        val nums1LeftMax = if (i == 0) Int.MIN_VALUE else nums1[i - 1]
        val nums2LeftMax = if (j == 0) Int.MIN_VALUE else nums2[j - 1]
        val nums1RightMin = if (i == m) Int.MAX_VALUE else nums1[i]
        val nums2RightMin = if (j == n) Int.MAX_VALUE else nums2[j]

        return if ((m + n) % 2 == 0) {
            val leftMax = maxOf(nums1LeftMax, nums2LeftMax)
            val rightMin = minOf(nums1RightMin, nums2RightMin)
            (leftMax + rightMin).toDouble() / 2
        } else {
            val leftMax = maxOf(nums1LeftMax, nums2LeftMax).toDouble()
            leftMax
        }
    }
}

解法3：分治

思路

我们可以从简单理想的情况开始着手，逐步改变条件，看需要考虑的因素会发生什么变化。

理想情况

假设m + n是奇数，中位数是第(m + n) / 2个数，令k = (m + n) / 2。

如果两数组长度相同，那么直接比较nums1[k / 2]和nums2[k / 2]的大小，就知道应该取哪个数是中位数了，这是很自然推导。

如果m != n，再比较nums1[k / 2]和nums2[k / 2]的大小，还能直接得出中位数是哪个吗？

不能，但是可以排除掉k / 2个元素不用再参与比较，这样其实就优化了时间复杂度。

比如nums1[k / 2] < nums2[k / 2]时，可得：

nums2[k / 2]有可能是第k大的数字，也有可能不是。
但是nums1[k / 2]绝对不是第k大的数。
nums1数组的前k / 2个元素也都不可能是第k大的数，因为nums1是从小到大排序的。

第k大的数是有可能出现在nums2的0到k / 2之中的，考虑极端情况：

如果nums1[k / 2]后续如果正好有个k / 2 - 1个元素比nums2[0]小，那么nums2[0]就是第k大的数。
如果nums1[k / 2]之后没有元素了，只能在在nums2[k / 2]后面再继续找第k大的数。

接下来怎么找第k大的数？

已经排除了k / 2个元素不用比较后，接着其实是要寻找第 k - k / 2 个数，寻找过程是一样的，这里就划分出了子问题，可以递归进行。
并且每次折半查找，时间复杂度是对数级别的。

边界

k一直缩减到1，就是最终想要得到的中位数。
如果数组没有第k / 2个数可选择，就取数组末尾的数比较。

m + n是偶数怎么办？

可以分别查找到左中位数和右中位数，再求平均值。

class Solution {
    fun findMedianSortedArrays(nums1: IntArray, nums2: IntArray): Double {
        val len1 = nums1.size
        val len2 = nums2.size
        val len = len1 + len2
        if (len % 2 == 0) {
            val left = len / 2
            val right = left + 1
            return (getKth(nums1, nums2, 0, 0, left) + getKth(nums1, nums2, 0, 0, right)) / 2.toDouble()
        } else {
            val mid = len / 2 + 1
            return getKth(nums1, nums2, 0, 0, mid).toDouble()
        }
    }
    
    private fun getKth(nums1: IntArray, nums2: IntArray, i1: Int, i2: Int, k: Int): Int {
        val len1 = nums1.size - i1
        val len2 = nums2.size - i2
        if (len1 > len2) return getKth(nums2, nums1, i2, i1, k)
        if (len1 == 0) return nums2[i2 + k - 1]
        if (k == 1) return minOf(nums1[i1], nums2[i2])
        val j1 = i1 + minOf(k / 2, len1) - 1
        val j2 = i2 + minOf(k / 2, len2) - 1
        return if (nums1[j1] < nums2[j2]) {
            getKth(nums1, nums2, j1 + 1, i2, k - (j1 - i1 + 1))
        } else {
            getKth(nums1, nums2, i1, j2 + 1, k - (j2 - i2 + 1))
        }  
    }
}

题目

题解