【西交ACM】298 ? 第N大的數

http://202.117.21.117/xjoj/problem_html/298.html

Description

一個簡單問題，在一串數中找出第N大的數

Input

包含多組數據，第一行輸入數據的組數T(<100)；每組數據包含2行，第一行2個數N，K，N表示這組數據中一共有N個數，K表示要找的是第K大的數，1<=K<=N<=100；第二行就是N個數（0 - 1000）。

Output

一共T行，每行輸出該組數據的第K大數。

Sample Input

2 4 2 1 2 8 7 7 5 87 136 769 178 85 55 974

Sample Output

7 87

使用快速排序，輸出指定項就可以了。 1 //author:pz 2 3 import java.util.Scanner; 4 5 public class Main{ 6 public static void main(String[] args) { 7 //int[] arr = {1,4,7,2,5,8,3,6,9}; 8 Scanner sc =new Scanner(System.in); 9 int t = sc.nextInt(); 10 for(int i = 0; i < t; i ++){ 11 int n = sc.nextInt(); 12 int k = sc.nextInt(); 13 int[] arr = new int[100]; 14 for(int j = 0; j < n; j ++){ 15 arr[j] = sc.nextInt(); 16 } 17 quickSort(arr); 18 // printArray(arr); 19 System.out.println(arr[arr.length - k]); 20 } 21 22 } 23 24 public static void printArray(int[] array){ 25 System.out.println("arr： "); 26 for(int i : array){ 27 System.out.print(i + ", "); 28 } 29 System.out.println(); 30 } 31 32 public static void quickSort(int[] a) { 33 quickSort(a, 0, a.length - 1); 34 } 35 36 private static void quickSort(int[] a, int start, int end) { 37 int left = start; 38 int right = end - 1; 39 int pivot = a[end]; 40 41 while (left < right) { 42 if (a[left] <= pivot) { 43 left++; 44 continue; 45 } 46 if (a[right] > pivot) { 47 right--; 48 continue; 49 } 50 swap(a, left++, right); 51 } 52 53 if (a[left] < pivot) { 54 left++; 55 } 56 swap(a, left, end); 57 58 if(left - 1 > start) { 59 quickSort(a, start, left - 1); 60 } 61 if(left + 1 < end) { 62 quickSort(a, left + 1, end); 63 } 64 } 65 66 private static void swap(int[] a, int i, int right) { 67 // TODO Auto-generated method stub 68 int temp = a[i]; 69 a[i] = a[right]; 70 a[right] = temp; 71 } 72 }

?

轉載于:https://www.cnblogs.com/pengzheng/archive/2013/04/18/3027746.html

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的【西交ACM】298 第N大的数的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。