本文共 4691 字，大约阅读时间需要 15 分钟。

微信搜索：编程笔记本。获取更多干货！

点击上方蓝字关注我，我们一起学编程

中位数

1 寻找两个有序数组的中位数

微信搜索：编程笔记本。获取更多干货！

题目描述：

给定两个递增排序的数组，长度分别为 m 和 n ，要求找出这两个数组的中位数。

1.1 合并数据法

由于这两组数据不在同一个集合内，因此给我们寻找中位数带来了一定的困难。一个最直观的想法就是，将数据合并到同一个数据集中，然后直接找出中间位置的数据即可。下面是参考代码：

时间复杂度：O(m+n)

class Solution {
   public:    double findMedianSortedArrays(vector
   
    & nums1, vector
    
     & nums2) {
           double ans;        int idx1 = 0;        /* 数组1的元素的游标 */        int idx2 = 0;        /* 数组2的元素的游标 */        vector
     
       nums;    /* 合并的数据集 */        while (idx1 < nums1.size() && idx2 < nums2.size()) {
               if (nums1[idx1] < nums2[idx2]) {
                   nums.push_back(nums1[idx1++]);            } else {
                   nums.push_back(nums2[idx2++]);            }        }        while (idx1 < nums1.size()) {
               nums.push_back(nums1[idx1++]);        }        while (idx2 < nums2.size()) {
               nums.push_back(nums2[idx2++]);        }        if (nums.size() % 2 == 0) {
               int idx = nums.size() / 2;            ans = (nums[idx - 1] + nums[idx]) / 2.0;        } else {
               int idx = nums.size() / 2;            ans = nums[idx];        }        return ans;    }};
     
    
   

1.2 二分查找法

上面的解法显然不是最优的解法，因为我们没有使用到“数组有序”这个条件。我们有一个直觉，这两个数组本来就是有序的，那么我们可不可以在 log 时间内求解问题呢？于是，我们想到了二分查找：在两个数组中寻找出较小的若干个数据，即可找到中间位置的数据。

时间复杂度：O(log(m+n))

微信搜索：编程笔记本。获取更多干货！

class Solution {
   public:    double findMedianSortedArrays(vector
   
    & nums1, vector
    
     & nums2) {
           double ans;        int totalLength = nums1.size() + nums2.size();                if (totalLength % 2 == 1) {
               ans = getKthElement(nums1, nums2, (totalLength + 1) / 2);        } else {
               ans = (getKthElement(nums1, nums2, totalLength / 2) + getKthElement(nums1, nums2, totalLength / 2 + 1)) / 2.0;        }                return ans;    }        int getKthElement(const vector
     
      & nums1, const vector
      
       & nums2, int k) {
           int ans;        int m = nums1.size();        int n = nums2.size();        int index1 = 0;        int index2 = 0;        while (true) {
               /* 边界情况 */            if (index1 == m) {
                      /* 中位数在数组2中 */                return nums2[index2 + k - 1];            }            if (index2 == n) {
                      /* 中位数在数组1中 */                return nums1[index1 + k - 1];            }            if (k == 1) {
                   ans = min(nums1[index1], nums2[index2]);                break;            }            /* 正常情况 */            int newIndex1 = min(index1 + k / 2 - 1, m - 1);            int newIndex2 = min(index2 + k / 2 - 1, n - 1);            int pivot1 = nums1[newIndex1];            int pivot2 = nums2[newIndex2];                        if (pivot1 <= pivot2) {
                   k -= newIndex1 - index1 + 1;                index1 = newIndex1 + 1;            } else {
                   k -= newIndex2 - index2 + 1;                index2 = newIndex2 + 1;            }        }                return ans;    }};
      
     
    
   

微信搜索：编程笔记本。获取更多干货！

2. 寻找数据流中的中位数

由于数据流中的数据总量不能确定，所以我们只能将已从数据流中获取的数据存入某种数据结构中，然后在取中位数时从数据结构中取。在这里，我们使用堆这种数据结构。

class MedianFinder {
    /***/public:    double findMedian() {
           if ((min.size() + max.size()) % 2 == 0) {
               return (min[0] + max[0]) / 2.0;        } else {
               return min[0];        }    }    void addNum(int num) {
           // 总数据数为偶数时将num插入到小根堆        if ((min.size() + max.size()) % 2 == 0) {
               if (max.size() > 0 && num < max[0]) {
                   max.push_back(num);                push_heap(max.begin(), max.end(), less
   
    ());                num = max[0];                pop_heap(max.begin(), max.end(), less
    
     ());                max.pop_back();            }            min.push_back(num);            push_heap(min.begin(), min.end(), greater
     
      ());        } else {
    // 总数据数为奇数时将num插入到大根堆            if (min.size() > 0 && num > min[0]) {
                   min.push_back(num);                push_heap(min.begin(), min.end(), greater
      
       ());                num = min[0];                pop_heap(min.begin(), min.end(), greater
       
        ());                min.pop_back();            }            max.push_back(num);            push_heap(max.begin(), max.end(), less
        
         ()); } }private: vector
         
           min; vector
          
            max;};
          
         
        
       
      
     
    
   

微信搜索：编程笔记本。获取更多干货！