## 寻找第K大

### 输入

`[1,3,5,2,2],5,3`

`2`

### 题目解答

#### 利用快排思想

```import java.util.*;

public class Finder {
public int findKth(int[] a, int n, int K) {
// write code here

int low = 0, high = n-1;
K = n - K;

int index = findKthCore(a, low, high, K);
return a[index];

}

public int findKthCore(int[] a, int low, int high, int K){

int mid = partion(a, low, high);

if(mid - low == K){
return mid;
}
if(mid - low > K){
return findKthCore(a, low, mid-1, K);
}
else{
return findKthCore(a, mid+1, high, K - (mid - low + 1));
}

}

public int partion(int[] a, int low, int high){

while(low < high){
while(low < high && a[high] >= a[low]){
high--;
}
swap(a, low, high);
while(low < high && a[low] <= a[high]){
low++;
}
swap(a, low, high);
}

return low;

}

public void swap(int[] a, int i, int j){

int temp = a[i];
a[i] = a[j];
a[j] = temp;
}
}
```

#### 通过堆实现

```import java.util.*;

public class Finder {
public int findKth(int[] a, int n, int K) {
// write code here

// 小顶堆
PriorityQueue<Integer> priorityQueue = new PriorityQueue<>();

for(int m : a){
// 堆元素数量不够K个或者待入堆元素比堆顶元素大
if(priorityQueue.size() < K || priorityQueue.peek() <= m){
priorityQueue.offer(m);
}
// 保持堆大小为K
if(priorityQueue.size() > K){
priorityQueue.poll();
}
}

return priorityQueue.peek();

}
}```

2022-12-14 17:48

2022-12-08 17:43

2022-12-29 10:23

2022-12-28 10:01

2022-12-10 18:47