- import java.util.Scanner;
- public class Main {
- //对数组array中下标start到end中的元素进行归并并排,求得该区间的降序排列
- public voidmergeSort(int[] array,intstart,int end) {
- if(end - start >= 1) {
- int[] leftArray = getHalfArray(array, start, end, 0);
- int[] rightArray = getHalfArray(array, start, end, 1);
- mergeSort(leftArray, 0, leftArray.length - 1);
- mergeSort(rightArray, 0, rightArray.length - 1);
- getMerge(array, start, leftArray, rightArray);
- }
- }
- //根据judge获取数组array区间start~end的一半元素
- public int[] getHalfArray(int[] array,intstart,intend,int judge) {
- int[] half;
- intlen = end - start + 1;
- if(judge == 0) {
- intlength = len / 2;
- half =new int[length];
- for(inti = 0;i < length;i++)
- half[i] = array[start + i];
- } else {
- intlength = len - len / 2;
- half =new int[length];
- for(inti = 0;i < length;i++) {
- half[i] = array[start + len / 2 + i];
- }
- }
- return half;
- }
- //合并数组array的左半边元素和右半边元素,返回降序排列
- public voidgetMerge(int[] array,intstart,int[] leftArray,int[] rightArray) {
- inti = 0, j = 0;
- while(i < leftArray.length && j < rightArray.length) {
- if(leftArray[i] >= rightArray[j])
- array[start++] = leftArray[i++];
- else
- array[start++] = rightArray[j++];
- }
- while(i < leftArray.length) array[start++] = leftArray[i++];
- while(j < rightArray.length) array[start++] = rightArray[j++];
- }
- public voidprintResult(int[] array,int[][] query) {
- int[] result =new int[query.length];
- for(inti = 0;i < query.length;i++) {
- int[] tempArray =new int[array.length];//此处获取array的克隆对象,要求地址也要改变。若直接赋值,两者地址是一样
- for(intj = 0;j < array.length;j++)
- tempArray[j] = array[j];
- intstart = query[i][0];
- intend = query[i][1];
- intk = query[i][2];
- if(k < 0 || k > end - start + 1)//防止k出界
- continue;
- mergeSort(tempArray, start - 1, end - 1);
- result[i] = tempArray[start - 1 + k - 1];
- }
- //输出结果
- for(inti = 0;i < result.length;i++)
- System.out.println(result[i]);
- }
- public static void main(String[] args) {
- Main test =new Main();
- Scanner in =new Scanner(System.in);
- intn = in.nextInt();
- int[] array =new int[n];
- for(inti = 0;i < array.length;i++)
- array[i] = in.nextInt();
- intm = in.nextInt();
- if(n > 1000 || m > 1000)
- return;
- int[][] query =new int[m][3];
- for(inti = 0;i < m;i++) {
- query[i][0] = in.nextInt();
- query[i][1] = in.nextInt();
- query[i][2] = in.nextInt();
- }
- test.printResult(array, query);
- }
- }
来源: http://www.bubuko.com/infodetail-1983074.html