连续段的中数

[编程题]连续段的中数

热度指数：550 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

牛牛得到了一个长度为n的正整数序列 $\{a_1,a_2,...a_n \}$ ，现在牛牛想要从里面取出一段连续的长度大于等于k的序列。

定义一个序列的“中数”为最大的整数x，使得序列中至少一半的数字大于等于x

牛牛想知道这个取出来的序列的中数最大可以是多少？

示例1

输入

5,3,[30,1,2,31,9]

输出

说明

选前四个数字组成[30,1,2,31]，中数为30

备注:



第一个参数n代表序列长度
第二个参数k代表取出的连续序列长度大于等于k
第三个参数vector a包含n个元素代表这个序列

算法知识视频讲解

C/C++

nbgao

class Solution {
public:
    /**
     * 连续段的中数
     * @param n int整型 
     * @param k int整型 
     * @param a int整型vector 
     * @return int整型
     */
    int solve(int n, int k, vector<int>& a) {
        int l=0, r=INT_MAX, m;
        while(l+1 < r){
            m = (l+r)>>1;
            int x=0, y=0, z=0;
            for(int i=0;i<k;i++)
                z += (a[i]>=m ? 1: -1);
            if(z >= 0){
                l = m;
                continue;
            }
            for(int i=0;i<n-k;i++){
                x += (a[i]>=m ? 1: -1);
                y = min(y, x);
                z += (a[i+k]>=m ? 1: -1);
                if(z >= y)
                    break;
            }
            if(z >= y)
                l = m;
            else
                r = m;
        }
        return l;
    }
};

发表于 2020-07-30 18:02:06 回复(0)

Python 3

牛客165300647号

随便做做...python3

class Solution:
def solve(self , n , k , a ):
# write code here
def Midnumber(liebiao):
length=len(liebiao)
l=sorted(liebiao)
i=int(length/2)
return l[i]
changdu=n
xulie=a
aa=[]
for i in range(0,changdu-k+1):
for j in range(i+k,changdu+1):
liebiao=xulie[i:j]
aa.append(Midnumber(liebiao))
return max(aa)

发表于 2022-04-23 14:22:06 回复(0)

牛客800183950号

import java.util.*;
public class Solution {
public int solve (int n, int k, int[] a) {
// write code here
int max=0;
while(k<=n){
int[] arr=new int[k];
for(int i=0;i<n-k+1;i++){
for(int j=i;j<k+i;j++){
arr[j-i]=a[j];
}
Arrays.sort(arr);
max=Math.max(max,arr[k/2]);
}
k++;
}
return max;
}
}

发表于 2021-06-17 19:47:46 回复(0)

yangeren

搞清题意大致就明白了，意思就是，从列表中取连续的大于等于k的数，比如k是2，列表是[1,2,3,4,5]，那么取的数列为[1,2], [1,2,3],[1,2,3,4],[1,2,3,4,5]，从这几个列表中，各取中位数，最后给出最大可能的中位数

发表于 2021-04-17 14:51:01 回复(0)

一只老风铃

容易知道，最大的中数一定在【最小值，最大值】区间内

直接二分查找即：mid=(l+r)/2

找到最后一个满足要求的中数

再实现一个判断一个数是否是中数的函数（具体做法记录该数的位置，研究出现次数大于k/2时，其首尾的长度）

class Solution {
public:
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param n int整型 
     * @param k int整型 
     * @param a int整型vector 
     * @return int整型
     */
    static bool judge(vector<int>&a,int num,int k)
    {
        vector<int> vec;
        for(int i=0;i<a.size();i++)
            if(a[i]>=num)
                vec.push_back(i);
        int len;
        if(k%2==0)
            len=k/2;
        else
            len=k/2+1;
        //i=>j表示出现次数多于len个  那么研究第I个 与第j个 之间的位置
        for(int i=0;i<vec.size();i++)
            for(int j=i+len-1;j<vec.size();j++)
            {
                //区间内满足出现二分之一以上
                if((vec[j]-vec[i]+1)<=(j-i+1)*2)
                    return true;
            }
        return false;
   
    }
    //研究Num是否是a的中数
    int solve(int n, int k, vector<int>& a) {
        // write code her
        vector<int> arr=a;
        sort(arr.begin(),arr.end());//从小到大排序
        //容易知道 最大的中数一定大于等于arr[0] 小于等于arr[len-1]
        //那么采取二分的方法 找到最后一个满足 是中数的数字
        
        int l=0;
        int r=arr.size()-1;
        while(l<=r)  //二分查找到最大的中数
        {
            int mid=(l+r)/2;
            int val=arr[mid]; //可能的中数
            if(judge(a,val,k))  //如果val是中数
                l=mid+1;
            else
                r=mid-1;
        }
        
       return arr[l-1];
    
        
    }
};

编辑于 2021-03-16 11:55:03 回复(0)