日期:2014-05-20 浏览次数:21237 次
import java.util.*;
import java.io.*;
public class select {
public static void main(String[] args) throws IOException{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] header = br.readLine().trim().split(" ");
int n = Integer.parseInt(header[0]);
int k = Integer.parseInt(header[1]);
int setNum = 1;
long startTime = System.currentTimeMillis();
while(n!=0){
int[] array = new int[n];
for(int i = 0; i < n; i++){
array[i] = Integer.parseInt(br.readLine());
}
int goal = quickselect(array,0,array.length-1,k);
System.out.println("Data set " + setNum + ": element " + k + " is " + goal);
setNum++;
header = br.readLine().trim().split(" ");
n = Integer.parseInt(header[0]);
k = Integer.parseInt(header[1]);
}
float spentTime = (System.currentTimeMillis()-startTime)/1000f;
System.out.println("Spent time: " + spentTime);
}
public static int partition(int[] list, int left,int right, int pivotIndex){
int pivotValue = list[pivotIndex];
int tmp = list[pivotIndex];
list[pivotIndex] = list[right];
list[right] = tmp;
int storeIndex = left;
for(int i = left; i < right; i ++){
if(list[i]<=pivotValue){
int tmp2 = list[storeIndex];
list[storeIndex] = list[i];
list[i] = tmp2;
storeIndex++;
}
}
tmp = list[right];
list[right] = list[storeIndex];
list[storeIndex] = tmp;
return storeIndex;
}
public static int quickselect(int[] list, int left, int right, int k){
if(left == right){
return list[left];
}
int pivotIndex = (left + right)/2;
int pivotNewIndex = partition(list,left,right,pivotIndex);
int pivotDist = pivotNewIndex - left + 1;
if(pivotDist == k){
return list[pivotNewIndex];
}else if(k < pivotDist){
return quickselect(list,left,pivotNewIndex - 1, k);
}else{
return quickselect(list,pivotNewIndex + 1, right, k - pivotDist);
}
}
}