题解 | #连续段的中数#

一.题目描述
NC566连续段的中数
一个长度为n的正整数序列a1,a2,a3......an，现在要从里面取出一段连续的长度大于等于k的序列。定义一个序列的“中数”为最大的整数x，使得序列中至少一半的数字大于等于x，求这个取出来的序列的中数最大可以是多少？
图片说明
二.算法(暴力)

首先题目要求取出一段连续长度大于等于k的序列，我们可以遍历所有长度等于k的序列，然后找到每一个序列的中数，然后找到中数中的最大值。对于如何找到中数我们可以想到类似中位数的概念，在一段有序的序列中类似中位数是不是就满足这里的中数的条件呢？所以对于每段长度等于k的序列我们可以进行排序，后找出其中位数，就是其中数了，所以题目的思路就很简单了，下面是完整代码：

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-1;j<n;j++){
                vector<int>res;
                //遍历数组中所有长度大于等于k的数组
                for(int r=i;r<=j;r++){
                    res.push_back(a[r]);
                }
                //对数字进行排序
                sort(res.begin(),res.end());
                int num=(j-i+1)/2;
                //返回下标是num/2的数
                ans=max(ans,res[num]);
            }
        }
        return ans;
    }
};

时间复杂度： $O(n^{3}log2(n))$ 因为要遍历数组所有的连续长度为k的子串，并且还有将每一个子串放入vector中所以，复杂度到了 $n^{2}$ 了，并且还要利用sort对vector进行排序，所以最后复杂度到了 $O(n^{3}log2(n))$
空间复杂度： $O(k)$ 需要开辟长度为k的空间来求出中数
优缺点：时间复杂度很高，但是便于理解代码实现简单
三.算法(二分)
首先我们要知道找出最大的中数这个最大的数就一定出现在数组中，在开始的时候如果将数组从小到大进行排序，那么是不是就符合二分查找的单调性了？我们先确定好边界l,r,对于每一次的中值mid进行一次check，看看是否可以实现，然后进行知道最后返回二分的答案，是不是就是最大中数了？？我们理清楚了二分的思路，我们将在代码注释中详细解释check函数，结合代码更容易理解，下面是完整代码：

class Solution {
public:
    //判断序列中至少一半的数字大于等于x
    bool check(vector<int>& b, int num, int k){
        vector<int> ans;
        for(int i=0;i<b.size();i++){
            if(b[i]>=num){
                //注意这块是存储大于等于判断值num的下标
                ans.push_back(i);
            }
        }
        int cnt;
        if(k%2){
            cnt=k/2+1;
        } else{
            cnt=k/2;
        }
        for(int i=0;i<ans.size();i++){
            for(int j=i+cnt-1;j<ans.size();j++){
                //判断是不是大于等于至少一半以上元素
                if((ans[j]-ans[i]+1)<=(j-i+1)*2){
                    return true;
                }
            }
        }
        return false;
    }
    int solve(int n, int k, vector<int>& a) {
        vector<int> b=a;
        sort(b.begin(),b.end());
        int l=0,r=a.size()-1;
        while(l<=r){ 
            int mid=(l+r)>>1; 
            if(check(a,b[mid],k)){
                l=mid+1;
            } else{
                r=mid-1;
            }
        }
        return b[l-1];
    }
};

时间复杂度： $O(n^{2}log2(n))$ 因为要遍历数组所有的连续长度为k的子串，并且还有将每一个子串放入vector中所以，复杂度到了 $n^{2}$ 了，并且还要利用二分进行查找，所以最后复杂度到了 $O(n^{2}log2(n))$
空间复杂度： $O(n)$ 需要开辟长度为n的空间来储存初始的vector
优缺点：时间复杂度相比之下比较低，但是二分代码实现不简单，需要注意细节