试题 算法训练 区间k大数查询 java题解
2021/4/8 12:10:59
本文主要是介绍试题 算法训练 区间k大数查询 java题解,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
资源限制 时间限制:1.0s 内存限制:256.0MB问题描述
给定一个序列,每次询问序列中第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。
出自:贵州电子商务职业技术学院
1 import java.util.Arrays; 2 import java.util.Scanner; 3 4 public class Main { 5 public static void main(String args[]){ 6 Scanner in=new Scanner(System.in); 7 //输入部分 8 int n=in.nextInt(); 9 int arr[]=new int[n]; 10 for (int i=0;i<n;i++){ 11 arr[i]=in.nextInt(); 12 } 13 //查询部分 14 int m=in.nextInt(); 15 int result[]=new int[m]; 16 int l,r,k; 17 for (int i=0;i<m;i++){ 18 l=in.nextInt(); 19 r=in.nextInt(); 20 k=in.nextInt(); 21 result[i]=Search(arr,l,r,k); 22 } 23 for (int i=0;i<result.length;i++){ 24 System.out.println(result[i]); 25 } 26 } 27 public static int Search(int arr[],int l,int r,int k){//这个方法是把从原来的数组 里面 的l到r的数据放到temp里面重新进行排序 28 int temp[]=new int[r-l+1];//这里注意因为l和r的下标是从1开始,不是从0开始,所以要加1,防止待会下标越界 29 int index=0; 30 int result=0; 31 for (int i=(l-1);i<r;i++){//当l为1,就代表从0开始,所以 l 要 -1 32 temp[index]=arr[i]; 33 index++; 34 } 35 Arrays.sort(temp);//使用java的方法快速的把temp里面的数据进行排序,然后倒序遍历就行了 36 for (int i=temp.length-1;i>=0;i--){//这部分把已经排序好的temp从len-1的下标到0遍历,如果k为0,那就是这波第k大的数值,找个变量保存直接返回 37 k--; 38 if (k==0){ 39 result=temp[i]; 40 } 41 } 42 return result; 43 } 44 }
这篇关于试题 算法训练 区间k大数查询 java题解的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现
- 2024-06-03为什么以及如何要进行架构设计权衡?
- 2024-05-31全网首发第二弹!软考2024年5月《软件设计师》真题+解析+答案!(11-20题)
- 2024-05-31全网首发!软考2024年5月《软件设计师》真题+解析+答案!(21-30题)
- 2024-05-30【Java】百万数据excel导出功能如何实现
- 2024-05-30我们小公司,哪像华为一样,用得上IPD(集成产品开发)?