区间大数查询

区间大数查询

问题描述
给定一个序列,每次询问序列中第一个数到第K个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 KSectionMaxNumber {
   public static void main(String[] args) {
       Scanner scanner = new Scanner(System.in);

       int n = scanner.nextInt(); //输入n,表示序列长度
       int[] arraysA = new int[n]; //给定的序列

       for (int i = 0; i < arraysA.length; i++) { //给数组赋值
           arraysA[i] = scanner.nextInt();
       }

       int m = scanner.nextInt(); //输入m,表示询问个数

      //声明创建一个二维数组
      //用于存放输入 m 次的 l、r、k
       int arrayB[][] = new int[m][3];
       for (int i = 0; i < m; i++) {
         arrayB[i][0] = scanner.nextInt();
         arrayB[i][1] = scanner.nextInt();
         arrayB[i][2] = scanner.nextInt();
       }

       for (int i = 0; i < m; i++) {
           System.out.println(kMaxNum(arraysA,arrayB[i][0],arrayB[i][1],arrayB[i][2]));
       }
   }

   //查找区间 l-r 中第 k 大的数的方法
   public static int kMaxNum(int[] arrayA,int l,int r,int k){
       int[] arrayC = new int[r - l  + 1];
       for (int i = 0; i < arrayC.length; i++) {//将要查询的区间里的元素拷贝到数组arrayC中
           arrayC[i] = arrayA[l + i - 1]; 
       }
       Arrays.sort(arrayC); //将数组升序排序
       return arrayC[arrayC.length - k]; //输出第k大的数
   }
}


运行结果
区间大数查询

区间大数查询

上一篇:.NET C#中处理Url中文编码问题


下一篇:Authentication in .NET Web Api