[LeetCode/LintCode] 题解丨阿里巴巴面试原题：两个排序数组的中位数

[hakunamatata11]

两个排序的数组 A 和 B 分别含有 m 和 n 个数，找到两个排序数组的中位数，要求时间复杂度应为 O(log (m+n))。

在线评测地址：

点击查看更多解法

说明

中位数的定义：

• 这里的中位数等同于数学定义里的中位数。
• 中位数是排序后数组的中间值。

如果有数组中有 n 个数且 n 是奇数，则中位数为 A[(n-1)/2]

• A[(n−1)/2]。

如果有数组中有 n 个数且 n 是偶数，则中位数为 (A[n / 2] + A[n / 2 + 1]) / 2

• (A[n/2]+A[n/2+1])/2.
• 比如：数组 A=[1,2,3]的中位数是 2，数组 A=[1,19]的中位数是 10 。

样例 1

输入:
A = [1,2,3,4,5,6]
B = [2,3,4,5]
输出: 3.5

样例 2

输入:
A = [1,2,3]
B = [4,5]
输出: 3

算法：归并

解题思路

• 最简单的思路是将两个数组合并，然后返回新数组的中位数。九章算法班中讲过，两个有序数组的合并是经典归并排序算法的一步，我们可以新开一个数组，保存合并后的结果。但是我们这样会做额外的工作，因为我们不必保存整个新数组，只需要知道新数组的中位数即可。
• 因此，更简便的方法是，使用双指针分别对两个数组遍历，比较两个指针下的元素大小，每次移动更小的指针，通过移动次数确定中位数的位置。

算法流程

• 令指针 p1 和 p2 分别指向两个数组，初始指向位置 0 。我们需要遍历(m + n)/2 + 1 次，每次比较两个位置的元素，在第 k 次比较时，较小的那个值就是两个数组中第 k + 1 小的数。如果一个指针已经走到了数组末尾，那么移动另一个指针，否则每次将指向较小数的指针后移，直到遍历到中位数。
• 为了将奇偶情况合并，在代码中用了 left 和 right 保存中间值，如果是奇数直接返回 right，如果是偶数就返回(left + right) / 2 。

复杂度分析

• 复杂度分析：

时间复杂度：O(m+n)，m 和 n 分别是两个数组的长度。双指针遍历两个数组，指针移动次数是 0(m+n)级。

• 空间复杂度：O(1)。

public class Solution {
    /*
     * @param A: An integer array
     * @param B: An integer array
     * @return: a double whose format is *.5 or *.0
     */
    public double findMedianSortedArrays(int[] A, int[] B) {
        int m = A.length, n = B.length;
        int p1 = 0, p2 = 0;
        int left = -1, right = -1;
        for (int i = 0; i < (m + n) / 2 + 1; i ++){
            left = right;
            // p2 右移
            if (p1 >= A.length || p2 < B.length && A[p1] > B[p2]){
                right = B[p2++];
            }
            // p1 右移
            else {
                right = A[p1++];
            }
        }
        return (m + n) % 2 == 1 ? right : (left + right) / 2.0;
    }
}

二分和快速选择等更多解法见：

点击查看更多解法

[Still4]

想了半天既然是排过序的数组，时间复杂度为什么是 O(log (m+n))，结果看解答里面果然是 O(m+n)

[Still4]

所以其实解法根本没有达到题目的要求啊，logn 的时间复杂度，只能用二分法