215. 数组中的第K个最大元素
题目描述
给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
输入输出
1
2
3
4
5
| 输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
|
基本思路
方法一：快排之后如果第[nums.length-k]位置的放好就返回
方法二：堆排序 善用 PriorityQueue
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
|
class Solution {
Random rand = new Random();
public int findKthLargest(int[] nums, int k) {
return QuickSort(nums, k, 0, nums.length-1);
}
public int QuickSort(int[] nums, int k, int low, int high) {
int index = rand.nextInt(high-low+1) + low;
int flag = nums[index];
nums[index] = nums[low];
int i = low, j = high;
while(i < j){
while(i < j && nums[j] >= flag) j--;
nums[i] = nums[j];
while(i < j && nums[i] <= flag) i++;
nums[j] = nums[i];
}
nums[i] = flag;
if(i == nums.length-k) return nums[i];
else if(i < nums.length-k) return QuickSort(nums, k, i+1, high);
else return QuickSort(nums, k, low, i-1);
}
}
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> heap = new PriorityQueue<>();
for (int num : nums) {
heap.add(num);
if (heap.size() > k) {
heap.poll();
}
}
return heap.peek();
}
}
|