package 第一章;
public class 選擇問題 {
/* 問題:設(shè)有一組N個(gè)數(shù)而要確定其中第K個(gè)最大者,我們稱之為選擇問題(selection problem) */
public static void main(String[] args) {
// 給定數(shù)組
int array[] = { 5491, 6897, 5892, 395, 3347, 2846, 2094, 5300, 7878, 3109 };
System.out.println(method1(array, 4));
// System.out.println(method2(array, 4));
}
/*
* 方法1: 將這N個(gè)數(shù)讀入一個(gè)數(shù)組中,在通過某種簡單算法,比如冒泡排序,異遞減順序?qū)?shù)組排序,然后返回 K上的元素
*/
public static int method1(int[] array, int k) {
// 排序后: 7878,6897,5892,5491,5300,3347,3109,2846,2094,395
sort(array);
return array[k - 1];
}
/*
* 方法2:將前K個(gè)元素讀入數(shù)組(已遞減順序)對其進(jìn)行排序.接著,將剩下的元素在逐個(gè)讀入.當(dāng)新元素被讀取時(shí),如果小于數(shù)組中的
* 第四個(gè)元素則忽略,否則就將其當(dāng)?shù)罃?shù)組中正確的位置.同時(shí)將數(shù)組中的一個(gè)元素移除數(shù)組,終止時(shí)返回第K個(gè)元素
*/
public static int method2(int[] array, int k) {
// 排序后: 7878,6897,5892,5491,5300,3347,3109,2846,2094,395
// 存儲K個(gè)元素的數(shù)組
int nArray[] = new int[k];
// 添加元素
for (int i = 0; i < k; i++) {
nArray[i] = array[i];
}
// 對數(shù)組排序
sort(nArray);
for (int i = k - 1; i < array.length; i++) {
// 如果當(dāng)前元素沒有最后一個(gè)大忽略
if (array[i] < nArray[k - 1]) {
continue;
}
// 創(chuàng)建一個(gè)存儲K+1個(gè)元素的數(shù)組,用來放新的較大的值
int[] kArray = new int[k + 1];
// 給新數(shù)組賦值
for (int y = 0; y < nArray.length; y++) {
kArray[y] = nArray[y];
}
// 新數(shù)組最后一個(gè)元素為較大值
kArray[kArray.length - 1] = array[i];
// 對新數(shù)組排序
sort(kArray);
// 將新數(shù)組的前K個(gè)元素賦值給老數(shù)組
for (int x = 0; x < nArray.length; x++) {
nArray[x] = kArray[x];
}
}
return nArray[k - 1];
}
// 方法3在第二章中講解
public static int method3(int array[], int k) {
return 0;
}
// 對數(shù)組進(jìn)行排序
public static int[] sort(int[] array) {
for (int x = 0; x < array.length - 1; x++) {
for (int y = x + 1; y < array.length; y++) {
if (array[x] < array[y]) {
int item;
item = array[x];
array[x] = array[y];
array[y] = item;
}
}
}
return array;
}
}
