题解 | #连续段的中数#

连续段的中数

http://www.nowcoder.com/practice/c14a99834969462bb412cd541870b57a

题意整理：

题目给出一个正整数数组，要求求出其中的长度至少为k的连续子数组的最大中数。一个数组的中数定义为数组中最大的满足数组中最少一半值大于等于该值的数。

对于一个已经排序完成的数组，简单的分析这个数组的中数。

对于含有奇数个数字的数组 $a [0 : 2 i]$ ，显然a[i]为中数。对于a[i]，大于等于该值的元素有i+1个，满足条件；而大于等于a[i+1]的只有i个，不满足最少一半。对于含有偶数个数子的数组 $a [0 : 2 i + 1]$ ，其中数为a[i+1]。对于a[i+1]，大于等于该数的元素有i+1个，满足条件，而对于a[i+2]，大于等于该数的有i个，不满足条件。

对于上述分析，可以发现对于一个长度为len的数组a，其中数必定为 $a [l e n / 2]$ ,对于奇数个元素的数组，这是数组最中间的元素；对于偶数个元素的数组，这是中间位置偏右的第一个元素。

方法一：枚举+排序

核心思想：

可以枚举每一个满足条件的区间，排序后确定中数，然后取得最大的中数即可。具体做法即枚举起点，然后从最小的满足条件的区间逐渐向后枚举到数组尾部，得到区间后对其排序并取得a[len/2]对答案进行更新。

核心代码：

class Solution {
public:
    int solve(int n, int k, vector<int>& a) {
        int ans = 0;
        for(int i = 0; i < n; ++i) {//枚举起点
            for(int j = i + k; j <= n; ++j) {//枚举终点（不包括）
                vector<int> res(a.begin() + i, a.begin() + j);//构造
                sort(res.begin(), res.end());
                int p = res[res.size() / 2];//取得中数
                ans = max(ans, p);
            }
        }
        return ans;
    }
};

复杂度分析：

时间复杂度： $O (n^{3} l o g n)$ 。二重循环开销为 $O (n^{2})$ ,排序开销为 $O (n l o g n)$ ,总开销为 $O (n^{3} l o g n)$

空间复杂度： $O (n)$ ,即开辟的用于排序的临时数组

方法二：枚举+双优先队列

核心思想：

方法一的时间复杂度很高，主要原因在于每次枚举区间的新终点都需要进行排序，实际上对于固定起点的区间枚举，是一个数据流中获取中位数的经典题目，可以采用双优先队列的方法，使得每个新元素加入时中位数的获取时间复杂度为O(1)而不是 $O (n l o g n)$ 。

双优先队列的思想很简单，因为需要获取的只是中位数，其他数字的顺序并不重要，所以只需要保证能够准确的获取中位数即可，所以可以使用一个小顶堆和一个大顶堆，小顶堆保存较大的一半数字，大顶堆保存较小的一半，插入元素时如果不满足条件就从一个队列弹出一个元素到另一个队列。取得中位数时，根据情况在两队列的队首根据元素数量进行判断即可。 alt

核心代码：

class Solution {
public:
    priority_queue<int, vector<int>, less<int>> queMin;//存放小的一半
    priority_queue<int, vector<int>, greater<int>> queMax;//存放大的一半
    //添加数字的函数
    void addNum(int num) {
        if (queMin.empty() || num <= queMin.top()) {
            //加入较小的队列，如果队列不平衡则弹出数字到较大队列
            queMin.push(num);
            if (queMax.size() + 1 < queMin.size()) {
                queMax.push(queMin.top());
                queMin.pop();
            }
        } else {
            //加入较大的队列，如果队列不平衡则弹出数字到较小队列
            queMax.push(num);
            if (queMax.size() > queMin.size()) {
                queMin.push(queMax.top());
                queMax.pop();
            }
        }
    }
    
    int solve(int n, int k, vector<int>& a) {
        int ans = 0;
        for(int i = 0; i < n; ++i) {//枚举起点
            queMin = priority_queue<int, vector<int>, less<int>>();
            queMax = priority_queue<int, vector<int>, greater<int>>();
            for(int j = 0; j < k - 1; ++j) {
                addNum(a[i + j]);
            }
            //相当于在数据留中寻找中位数
            for(int j = i + k - 1; j < n; ++j) {
                addNum(a[j]);
                //如果较小队列长度大，那么说明有奇数个数字，中位数是较小队列首元素
                //如果两队列等长，那么说明有两个符号的数字，取得较大队列首元素（更大）
                int p= queMin.size() > queMax.size() ? queMin.top(): queMax.top();
                ans = max(ans, p);
            }
        }
        return ans;
    }
};