题解 | #连续段的中数#

题目：

牛牛得到了一个长度为n的正整数序列,现在牛牛想要从里面取出一段连续的长度大于等于k的序列。定义一个序列的“中数”为最大的整数x，使得序列中至少一半的数字大于等于x,牛牛想知道这个取出来的序列的中数最大可以是多少？

方法一：暴力

暴力算法的思路就是逐个枚举可能的区间，将该区间复制到新数组arr中，并进行排序，找到中间值，取最大的中间值

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int solve (int n, int k, int[] a) {
        // write code here
        int res=Integer.MIN_VALUE;
        for(int i=0;i<=n-k;i++){
            int l=i,r=l+k-1;
            for(;r<n;r++){
                int[]arr=new int[r-l+1];
                int len=arr.length;
                System.arraycopy(a,l,arr,0,len);
                Arrays.sort(arr);
                res=Math.max(res,arr[len/2]);
            }
        }
        return res;
    }
}

复杂度：

• 时间复杂度：$O\left(n^{3}lo{g}_{2}n\right)O(n^\{3\}log\_\{2\}n)$O(n3log2​n),外面双层循环，内层排序算法的时间复杂度为$O\left(nlo{g}_{2}n\right)O(nlog\_\{2\}n)$O(nlog2​n)
• 空间复杂度：$O\left(n\right)O(n)$O(n),额外数组的大小不超过n

方法二：二分查找

思路：

数组中的每个数都可能是中位数，因此对给定数组a排序并且二分查找中位数，需要构造一个判定某个数是否是一段序列中位数的函数；如果满足中位数的条件，中位数也许可以更大，因此向右边区间查找，如果不满足，则向左边区间查找，因为找到mid时,l=mid+1，因此最终返回的值是a[l-1]

具体方法为：

• 对所给数x，记录比它大的数的下标

• 我们需要找到至少len个数比x大，如果k是偶数，至少找到k/2个数比x大，如果是奇数，则是k/2+1个数

• 则i从0开始枚举，j至少从i+len-1开始枚举，当每段区间内元素个数为temp[j]-temp[i]+1的一半数量小于等于j-i+1，则是正确的

import java.util.*;
import java.util.List;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @param a int整型一维数组 
     * @return int整型
     */
    public int solve (int n, int k, int[] a) {
        // write code here
        int[]arr=new int[n];
        System.arraycopy(a,0,arr,0,n);
        Arrays.sort(arr);
        int l=0,r=n-1;
        while(l<=r){
            int mid=(l+r)>>1;
            if(judge(arr[mid],a,k))l=mid+1;
            else r=mid-1;
        }
        return arr[l-1];
    }
    boolean judge(int x,int[]a,int k){
        List<Integer>temp=new ArrayList<>();
        for(int i=0;i<a.length;i++){
            if(a[i]>=x)temp.add(i);//存储比x大的值的下标
        }
        int len=0;//需要至少存在len个元素比x大
        if(k%2==0)len=k/2;//如果是偶数，只需要找到k/2个比x大的数，奇数则需要再增加1
        else len=k/2+1;
        //区间长度为temp.get(j)-temp.get(i)+1
        for(int i=0;i<temp.size();i++){
            for(int j=i+len-1;j<temp.size();j++){
               if((temp.get(j)-temp.get(i)+1)<=(j-i+1)*2)return true;
            }
        }
        return false;
    }
}

复杂度：

• 时间复杂度：$O\left(n^{2}lo{g}_{2}n\right)O(n^\{2\}log\_\{2\}n)$O(n2log2​n),二分查找的时间复杂度为$O\left(lo{g}_{2}n\right)O(log\_\{2\}n)$O(log2​n),judge函数的时间复杂度最差为$O\left(n^2\right)O(n^\{2\})$O(n2)
• 空间复杂度：$O\left(n\right)O(n)$O(n),两个辅助数组大小均不超过n