LeetCode 题解——Median of Two Sorted Arrays

发表于 | 分类于 | 阅读次数:
字数统计: 813 字

LeetCode 题解——Median of Two Sorted Arrays

题意

给定两个有序数组，求这两个有序数组中所有数的中位数

题解

首先理解什么是中位数，中位数把这两个数组中的所有的数有序放到一起，排在中间的那一个数（或者两个数）就是中位数，我们也可以从另外一个角度去看，中位数作为边界把这些数分割成两半。这两边的数的个数是相等的。

对于这两个数组就相当于每个数组都有一个数把这个数组分割成两半：

这里考虑使用二分法求解，对于两个数组，两边的数的个数是相等的。由此，考虑一种分割情况，我们可以假设A数组从i点分割，这样因为两边的数的个数相等很容易算得B数组的分割点j=(n+m+1)/2-i，对于每一种分割有三种情况：

  1. A[i]>=B[j-1] && B[j]>=A[i-1]这种情况下，刚好取得中位数
  2. A[i]<B[j-1] 这种情况下，表示我们选取的i点过小，可以通过二分进一步缩减范围
  3. B[j]<A[i-1] 这种情况下，表示我们选取的i点过大，可以通过二分进一步缩减范围

除此之外另外还要注意几点：

  1. 我们选取的i要从数组数量较小的那个数组中选取，因为如果从数组数量大的数组中选取的话，可能导致选取的i较小，使得计算出的j值大于B数组中的元素个数
  2. 存在一些特殊情况在端点分割的特殊情况，比如i=0，i=n，j=0，j=m的这些情况。在这样的情况下，我们可以只需要计算左边数的最大值，和右边数的最小值即可。
  3. 最后的结果要对总数是奇数还是偶数进行讨论，如果是奇数的话，表示中位数是左边那一堆中的最大值；如果是偶数的话，中位数中左边一堆数的最大值和右边一堆书的最小值的平均值。

代码（C++）

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
38
39
40
41
42
43
44
45
class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int n = nums1.size(), m = nums2.size();
        // 对小的数组进行分割
        if(n > m)
        {
            swap(nums1, nums2);
            swap(n,m);
        }
        // 二分法确定两个界限
        int i, j, iMin = 0, iMax = n;
        while(iMin <= iMax)
        {
            i = (iMin + iMax)/2 ;
            j = (m+n+1)/2 - i;
            // i的取值过大
            if(i > iMin && nums1[i-1] > nums2[j])
            {
                iMax = i - 1;
            }
            // i的取值过小的情况
            else if(i < iMax && nums1[i] < nums2[j-1]) 
            {
                iMin = i + 1;
            }
            // 找到中位数
            else{
                int left = 0;
                if(i == 0) left = nums2[j-1];
                else if(j == 0) left = nums1[i-1];
                else left = max(nums1[i-1], nums2[j-1]);
                // 总数是奇数的时候
                if ( (m + n) % 2) return left;
                
                int right = 0;
                if(i == n) right = nums2[j];
                else if(j == m) right = nums1[i];
                else right = min(nums1[i], nums2[j]);
                return (left + right)/2.0;
            }
        }
        return 0.0;
    }
};

更多LeetCode题解，欢迎查看我的GitHub项目