4. 寻找两个有序数组的中位数 - 力扣（LeetCode）

发表于 更新于 分类于 阅读次数： Disqus：

题目描述

给定两个大小为 m 和 n 的有序数组 nums1 和 nums2。 请你找出这两个有序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。 你可以假设 nums1 和 nums2 不会同时为空。 示例1：

1
2
3
nums1 = [1, 3]
nums2 = [2]
则中位数是 2.0

示例2：

1
2
3
nums1 = [1, 2]
nums2 = [3, 4]
则中位数是 (2 + 3)/2 = 2.5

题解

自己能够想到的是将两个有序数组进行归并排序，然后根据奇偶取中位数。但这样做的时间复杂度为o(m+n)，是不符合题意。 最后参考官方题解，写出了时间复杂度为o(log(m+n))的程序。 首先回顾中位数定义是对于n个数据，求取中位数首先将其排序，若n为奇数，则中位数为第(n+1)/2个数；若n为偶数，则中位数是第n/2个数和第n/2 + 1个数之和的平均数。 现在我们换种思路，已知两个有序数组和nums1（元素个数为n）和nums2(元素个数为m)。对于nums1，将其从位置i处划分成两部分，我们有n+1种划分方式。i的取值为[0, n]。当i=0，左边有0个元素，右边有n个元素；当i=n，左边有n个元素，右边有0个元素；当i介于0到n之间，左边有i个元素，右边有n-i个元素。划分的左边区域的最大值记为lmax1，划分的右边区域的最小值记为rmin1。lmax1 = nums1[i - 1]，rmin1 = nums1[i]。 同理对于nums2数组，我们在位置j处划分。有lmax2 = nums2[j - 1]，rmin2 = nums2[j]。 现在若我们能保证i + j = (n + m + 1) / 2且lmax1 <= rmin2，lmax2 <= rmin1，则nums1与nums2的左边区域和nums1与nums2的右边区域元素个数相等，且左边 <= 右边。 这种情况下，很容易找到中位数，当n+m为偶数时，中位数为max(lmax1, lmax2)与min(rmin1,rmin2)的平均数；当n+m为奇数，中位数为max(lmax1, lmax2)。 位置i的调整采用二分的方式，当lmax1 > rmin2时，说明nums1左边元素偏大，需将i减小，此时j增大（j = (n + m + 1) / 2 - i）,当lmax2 > rmin1时，说明num2左边元素偏大，需将j减小，此时i增大。

题目代码

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
36
37
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int m = nums1.size();
        int n = nums2.size();
        if(m > n){
            return findMedianSortedArrays(nums2, nums1);
        }
        else{
            int low = 0, high = m;
            int lmax1, lmax2, rmin1, rmin2, i, j;
            while(low <= high){
                i = (low + high) / 2;
                j = (m + n + 1) / 2 - i;
                lmax1 = i == 0?INT_MIN:nums1[i - 1];
                rmin1 = i == m?INT_MAX:nums1[i];
                lmax2 = j == 0?INT_MIN:nums2[j - 1];
                rmin2 = j == n?INT_MAX:nums2[j];
                if(lmax1 > rmin2){
                    high = i - 1;
                }
                else if(lmax2 > rmin1){
                    low = i + 1;
                }
                else{
                    if((m + n) % 2 == 0){//偶数
                        return (max(lmax1, lmax2) + min(rmin1, rmin2)) / 2.0;
                    }
                    else{//奇数
                        return max(lmax1, lmax2);
                    }
                }
            }
            return 0.0;
        }
    }
};

执行结果