日期:2014-05-20 浏览次数:20908 次
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); } } }