Leetcode - Median of Tow Sorted Arrays

题目概述

There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).

解题报告

这道题在处理题目的模型和实现上都稍微有点难度。

这里我们先讨论普通的二分查找，就是说我们要确定一个数字的具体排位的时候，比如说第N大的数字。可以维护一个优先队列，期望时间复杂度就是O(nlogm)。《编程珠玑》里面提到的一种更好的方法：借助快排的思想，可以将复杂度优化到O(n)。

题意解析

不过，上面是无序的情况，如果是有序的数字呢？显然，可以O(1)找到对应排位的数字，这个也就是我们要突破的重点。两个有序的序列，找到其中的中位数字。首先我们怎么理解可以帮助我们呢?中位数是分割一个序列为两个部分，这两个的部分的数字个数相等。中位数是说排在(n/2)或(n/2, n/2 + 1)的数字。

所以这道题目就是要我们找到一个中位数，使得两个数列合在一起可以被分成数目相等的两个部分。这样我们重新定义了问题，使得理解更加具体。

解决步骤

  • a[0], a[1], a[2] … a[i - 1] median a[i + 1], a[i + 2] … a[n]
    b[0], b[1], b[2] … b[j - 1] median b[j + 1], b[j + 2] … b[m]
  • a[i - 1] < b[j] (a)
    b[j - 1] < a[i] (b)
  • a[i] == b[j] // 找到了median，中位数不一定同时存在于两个数组中

如何找到相应的i与j呢？切入口在于我们二分的对象是什么。
这里有个隐藏的条件：i + j = n - i + m - j(中位数两边的数字个数相等)，也就是说i确定了，j也就可以确定了，这个结论很好，我们只需要枚举其中一个就能解决问题。通常我们需要枚举长度短的序列，这样边界就不会溢出。

重要结论1：i = (m + n + 1) / 2 - j。
这样我们遍历 i 亦或 j 中的一个，就能确定另外一个的值了。
我们来搜索 i ：

  1. 如果 a[i] == b[j]，那么我们就找到了最终的结果。
  2. 如果 a[i] > b[j] 说明我们要调整 i，使得a[i]减小，b[j]则相对增大。
  3. 对于2，反之亦然。

不过，这里要考虑一个情况，要找到的值未必都在两个数列中。比如：[1,2,3,4,5] 和 [6]。更特殊：[1,2], []。
这个也是问题的第二个关键点。
首先，假设较短的数列已经触及边界，同时不满足约束条件(a), (b)，那么就意味着我们已经找到答案了。原因在于每次的划分都是平衡划分，一个数列触及了边界，答案也就一定在另外一个数列当中，而答案在另一个数列当中的时候就是一个普通的二分查找。显然较短的数列会更快碰到边界。
结论2：我们每次搜索需要检查较短数列的边界在合理范围之内。

搜索结束后，正确答案在哪里？
如果两个数列的长度总和为奇数，那么搜索位置较大的那个即为所求。否则要计算两个位置较大的和后继位置较小的数字的均值：

max(a[i-1], b[j-1]), odd
(max(a[i-1], b[j-1]) + min(a[i], b[j])) / 2, even

边界条件的处理，当 i == 0 或 i == length of list 的时候，这个时候搜索也结束了。对于 j 亦然。

程序清单

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
public class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int[] longNum;
        int[] shortNum;
        if (nums1.length > nums2.length) {
            longNum = nums1;
            shortNum = nums2;
        } else {
            longNum = nums2;
            shortNum = nums1;
        }
        int left = 0, right = shortNum.length, half = (longNum.length + shortNum.length + 1) / 2;
        double leftHalf = 0.0, rightHalf = 0.0;
        while (left <= right) {
            int i = (left + right) / 2;
            int j = half - i;
            if (i < shortNum.length && shortNum[i] < longNum[j - 1])
                left = i + 1;
            else if (i > 0 && longNum[j] < shortNum[i - 1])
                right = i - 1;
            else {
                if (i == 0) leftHalf = longNum[j - 1];
                else if (j == 0) leftHalf = shortNum[i - 1];
                else leftHalf = Math.max(shortNum[i - 1], longNum[j - 1]);
                if ((shortNum.length + longNum.length) % 2 == 1)
                    return leftHalf;
                if (i == shortNum.length) rightHalf = longNum[j];
                else if (j == longNum.length) rightHalf = shortNum[i];
                else rightHalf = Math.min(shortNum[i], longNum[j]);
                return (leftHalf + rightHalf) / 2.0;
            }
        }
        return 0;
    }
}