根據快排的思路來做
題目簡化為求某個數組的最中間的兩個數，然後根據快排的思路進行排除即可，相對于快排大大減少了比較的次數，代碼如下： import java.util.*;
public class Main{
// 利用快排的思路尋找一個數組中第target大的數
private static int getTarget(int[] data, int target){
int mid=data[0], l=0, r=data.length-1;
while(l < r){
while(l < r && data[r] > mid)
r--;
if(l < r)
data[l++] = data[r];
while(l < r && data[l] < mid)
l++;
if(l < r)
data[r--] = data[l];
}
data[l] = mid;
if(l+1 == target)
return data[l];
else if(l+1 < target)
return getTarget(Arrays.copyOfRange(data, l+1, data.length), target-(l+1));
else
return getTarget(Arrays.copyOfRange(data, 0, l), target);
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNextInt()){
int n = sc.nextInt();
if(n == 0)
break;
int[] data = new int[n];
for(int i=0; i
data[i] = sc.nextInt();
// 尋找一個數組中最中間的兩個數
int mid1 = (data.length+1)/2;
int mid2 = (data.length+2)/2;
System.out.println((getTarget(data, mid1)+getTarget(data, mid2))/2);
}
sc.close();
}
}