题目
给定整数数组 $nums$ 和整数 $k$，请返回数组中第 $k$ 个最大的元素。
请注意，你需要找的是数组排序后的第 $k$ 个最大的元素，而不是第 $k$ 个不同的元素。
你必须设计并实现时间复杂度为 $O(n)$ 的算法解决此问题。
示例 1:
1
2
| 输入: [3,2,1,5,6,4], k = 2
输出: 5
|
示例 2:
1
2
| 输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
|
提示：
- $1 <= k <= nums.length <= 10^{5}$
- $-10^{4} <= nums[i] <= 10^{4}$
解析
见堆的java实现
实现
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
| class Solution {
public class MaxHeap{
private int size;
private ArrayList<Integer> data;
public MaxHeap(){
data = new ArrayList<>();
}
public MaxHeap(int[] arr){
data = new ArrayList<>();
for(int i=0;i<arr.length;i++){
data.add(arr[i]);
}
int lastP = getParent(data.size()-1);
for(int i=lastP;i>=0;i--){
siftDown(i);
}
}
public int size(){
return this.data.size();
}
public boolean isEmpty(){
return this.data.isEmpty();
}
public int getParent(int idx){
return (idx-1)/2;
}
public int getLeftChild(int idx){
return idx*2+1;
}
public int getRightChild(int idx){
return idx*2+2;
}
public void swap(int i,int j){
Integer temp = data.get(i);
data.set(i,data.get(j));
data.set(j,temp);
}
public void siftUp(int k){
while(k>0&&data.get(getParent(k))<data.get(k)){
swap(k,getParent(k));
k = getParent(k);
}
}
public void siftDown(int k){
while(getLeftChild(k)<data.size()){
int j = getLeftChild(k);
if(getRightChild(k)<data.size()){
if(data.get(j)<data.get(getRightChild(k))){
j = getRightChild(k);
}
}
if(data.get(j)>data.get(k)){
swap(j,k);
k = j;
}
else{
break;
}
}
}
public Integer poll(){
Integer res = data.get(0);
data.set(0,data.get(data.size()-1));
data.remove(data.size()-1);
siftDown(0);
return res;
}
public Integer peek(){
return data.get(0);
}
public void add(Integer element){
data.add(element);
siftUp(data.size()-1);
}
}
public int findKthLargest(int[] nums, int k) {
MaxHeap heap = new MaxHeap(nums);
for(int i=0;i<k-1;i++){
heap.poll();
}
return heap.peek();
}
}
|
