題目要求：
撰寫程式，對任意輸入的若干個不相同的整數，輸出其第k大的數
決議：
我們采用分治法解決這道題，
把這些數放在一個陣列中，用分治法的話，我們可以想到，怎樣分治？
把一個陣列分成若干個大小相等的子陣列，然后在這些子陣列中取中位數，再取這些中位數的中位數，用這個數就可以把陣列劃分為一個比它大的和比它小的陣列，通過用這個數和我們要求的數進行比較，若等于它，則直接回傳這個數，若小于，則遞回的對這個數前面的陣列的這些數進行分治策略，若大于，則遞回的對這個數后面的陣列的這些數進行分治策略，
\(main()\)里只有一個\(SelectK()\)方法，中包含有兩個主要的方法，分別為取中位數\(Median()\)和劃分\(Divide()\)方法，
\(Median()\)：
首先，我們把陣列分為5個一組（聽說經過證明，5個一組劃分最科學），然后取每組的中位數，這時用的是\(Median()\)方法，具體的對每5個連續的數進行排序，然后把每組中的中位數即第3個數交換到陣列的最左邊，如果這些轉移的數的個數多于5個，就再次呼叫\(Median()\)方法，直到最左邊的數是這個陣列的中位數的中位數，
\(Divide()\)：
介紹劃分方法，當求得中位數的中位數后，我們就以這個數為基準，把當前進行排序的陣列的段落進行劃分，小于基準數的交換到基準數的左邊，大于的交換至右邊，然后比較要求的那個數和基準數是否相等，如果相等，則回傳；若小于基準數，則遞回左邊的子陣列；若大于基準數，則遞回右邊的子陣列，
到這里，就是簡單介紹一下這道題，這道題的主要演算法在網上叫BFPRT演算法，有興趣的同學可以去搜一下，如果不想搜的話，可以直接看我之前寫的具體講這道題分治演算法背后的演算法思想的文章分治策略-選擇問題，
Java代碼：
static void swap(int[]arr,int i,int j){
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
static void sortArr(int[] arr,int a,int b){
for(int i=a;i<b;i++){
for(int j=i+1;j<=b;j++){
if(arr[i]<arr[j])
swap(arr,i,j);
}
}
}
//找中位數的中位數
static int Median(int[] arr,int a,int b){
if(a==b)
return a;
int i=0;
int n=0;
for(i=a;i<b-5;i+=5){
sortArr(arr,i,i+4);
n = i - a;
swap(arr,a+n/5,i+2);
}
//下面是剩余的數
int last = b-i+1;
if(last>0){
sortArr(arr,i,i+last-1);
n = i - a;
swap(arr,a+n/5,i+last/2);
}
n/=5;
if(n==a)
return a;
return Median(arr,a,a+n);
}
//劃分
static int Divide(int[]arr,int a,int b,int m){
swap(arr,m,a);
int i = a;
int j = b;
int flag = arr[a];
while (i<j){
while (arr[j]<=flag && i<j)
j--;
arr[i] = arr[j];
while (arr[i]>=flag && i<j)
i++;
arr[j] = arr[i];
}
arr[i] = flag;
return i;
}
static int SelectK(int[] arr,int a,int b,int k){
int m = Median(arr,a,b);
int i = Divide(arr,a,b,m);
int x = i-a+1;
if(x==k)
return arr[i];
if(x>k)
return SelectK(arr,a,i-1,k);
return SelectK(arr,i+1,b,k-x);
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
System.out.println("請輸入要求的第k大的k：");
int k = in.nextInt();
int[] arr = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16,17,18,19,20,21,22,23,24,25,100,99,98,97,96,95,94,93,92,91,
90,89,88,87,86,85,84,83,82,81,80,79,78,77,76,75,74,73,72,71,70,69,68,67,66,65,64,63,62,61,60,59,58,57,56,55,54,
53,52,51,50,49,48,47,46,45,44,43,42,41,40,39,38,37,36,35,34,33,32,31,30,29,28,27,26};
// System.out.println(arr.length);
System.out.println("第"+k+"大為："+SelectK(arr,0,arr.length-1,k));
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/49718.html
標籤：其他
下一篇：二叉樹的存盤結構