Java 区间k大数查询

ゝ一世哀愁。 2022-04-22 22:42 182阅读 0赞

问题描述

给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。

输入格式

第一行包含一个数n，表示序列长度。

第二行包含n个正整数，表示给定的序列。

第三个包含一个正整数m，表示询问个数。

接下来m行，每行三个数l,r,K，表示询问序列从左往右第l个数到第r个数中，从大往小第K大的数是哪个。序列元素从1开始标号。

输出格式

总共输出m行，每行一个数，表示询问的答案。

样例输入

5  
1 2 3 4 5  
2  
1 5 2  
2 3 2

样例输出

4  
2

数据规模与约定

对于30%的数据，n,m<=100；

对于100%的数据，n,m<=1000；

保证k<=(r-l+1)，序列中的数<=106。

代码：

import java.util.Arrays;
    import java.util.Scanner;
    
    public class Test {
        public static void main(String[] args) {
            Scanner sc = new Scanner(System.in);
            int n = sc.nextInt();
            int arr[] = new int[n];
            for (int i =0;i<n;i++){
                arr[i] = sc.nextInt();
            }
            int n2 = sc.nextInt();
            while (n2 != 0){
                int a = sc.nextInt();
                int r = sc.nextInt();
                int K = sc.nextInt();
                int count = 0;
                int arr2[] = new int[r-a+1];
                for(int j =a-1;j<r-1;j++){
                    arr2[count] = arr[j];
                    count++;
                }
                Arrays.sort(arr2);
                System.out.println(arr2[r-a-K+2]);
            }
            n2--;
        }
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，182人围观）

还没有评论，来说两句吧...

相关阅读

相关蓝桥杯算法训练区间k大数查询（排序、查找）

算法训练区间k大数查询时间限制：1.0s 内存限制：256.0MB 问题描述给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。输入格式第一行

忘是亡心i/ 2024年02月17日 20:43/ 0 赞/ 43 阅读

相关【蓝桥杯】ALGO-1 区间k大数查询排序查找

ALGO-1 区间k大数查询资源限制时间限制：1.0s 内存限制：256.0MB 问题描述给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪

末蓝、/ 2022年12月03日 09:14/ 0 赞/ 147 阅读

相关算法训练区间k大数查询

> 问题描述 > 给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。 > 输入格式 > 第一行包含一个数n，表示序列长度。 > 第二行包含n个正

傷城~/ 2022年09月28日 13:07/ 0 赞/ 150 阅读

相关蓝桥杯 - 区间k大数查询

给定一串数字，求固定区间的第N大数。因为区间是固定的，是不可以预处理的，所以每有一个区间就拿出这些数字排序，然后输出第N大的数即可 `memcpy(b, a+l, s

以你之姓@/ 2022年06月03日 10:53/ 0 赞/ 171 阅读

相关蓝桥杯 - 区间k大数查询

根据输入的左右区间，放入一个数组，然后进行排序，左位置加上第几位减去1就是这个数字所在的位置 include<cstdio> include<algorith

太过爱你忘了你带给我的痛/ 2022年06月01日 02:35/ 0 赞/ 203 阅读

相关 ALGO-1 区间k大数查询排序查找

问题描述给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。输入格式第一行包含一个数n，表示序列长度。第二行包含n个正整数，表示

Dear 丶/ 2022年05月31日 11:13/ 0 赞/ 182 阅读

相关 Java 区间k大数查询

问题描述给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。输入格式第一行包含一个数n，表示序列长度。第二行包含n个正整数，表示给定的序列。第

ゝ一世哀愁。/ 2022年04月22日 22:42/ 0 赞/ 183 阅读

相关蓝桥杯基础算法训练区间k大数查询（模拟+排序）

问题描述给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。输入格式第一行包含一个数n，表示序列长度。第二行包含n个正整数，表示给定的序列。第

小咪咪/ 2022年03月21日 14:41/ 0 赞/ 174 阅读

相关蓝桥杯算法训练（一）区间k大数查询 C语言

区间k大数查询 C语言问题描述给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。输入格式第一行包含一个数n，表示序列长度。第二行包含n个

小灰灰/ 2022年03月21日 11:25/ 0 赞/ 275 阅读

相关算法训练区间k大数查询(水题)

问题描述给定一个序列，每次询问序列中第l个数到第r个数中第K大的数是哪个。输入格式第一行包含一个数n，表示序列长度。第二行包含n个正整数，表示给定的序列。第

清疚/ 2022年03月07日 21:30/ 0 赞/ 551 阅读