1、使用HashMap或者Queue保存
如果是少量的數(shù)據(jù)柳沙，比如K=2,3等可以使用岩灭，如2，保存到HashMap找最大赂鲤，合計(jì)為2N次比較川背。
2、典型解法：快速排序分組蛤袒。
在數(shù)組中找到第k大的元素
取基準(zhǔn)元素熄云，將元素分為兩個(gè)集合，一個(gè)集合元素比基準(zhǔn)小妙真，另一個(gè)比基準(zhǔn)大 缴允，三種情況。
1.比基準(zhǔn)大的元素?cái)?shù)目標(biāo)志位m正好為k-1珍德，基準(zhǔn)就是目的元素练般。
2.比基準(zhǔn)大的元素標(biāo)志位m小于k, 那么就在比基準(zhǔn)小的集合里面找第(k-m)大的元素
3.若是比基準(zhǔn)大的元素為m大于k，那就繼續(xù)在該集合里面找第k大的元素锈候。
如下是代碼：
static void findKMax(int[] arr, int left, int right, int k) {
int temp = partition(arr, left, right);
if (temp == k - 1) {
System.out.println(arr[temp]);
} else if (temp > k - 1) {
findKMax(arr, left, temp - 1, k);
} else {
findKMax(arr, temp + 1, right, k - temp);
}
}
static int partition(int[] arr, int left, int right) {
int temp = arr[left];
while (left < right) {
while (temp >= arr[right] && left < right)
--right;
arr[left] = arr[right];
while (temp <= arr[left] && left < right)
++left;
arr[right] = arr[left];
}
arr[right] = temp;
return right;
}
public static void main(String[] args) {
int[] arr = new int[] { 12, 23, 2, 3, 2, 432, 43, 534, 5, 345, 3453, 53, 43 };
findKMax(arr,0,arr.length - 1,2);
}
