优先级队列
# 215. 数组中的第K个最大元素 (opens new window)
方法一：堆
class Solution {
public int findKthLargest(int[] nums, int k) {
PriorityQueue<Integer> pq = new PriorityQueue<>();
for(int num:nums){
pq.offer(num);
if(pq.size()>k){
pq.poll();
}
}
return pq.peek();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
2
3
4
5
6
7
8
9
10
11
12
方法二：快排
class Solution {
public int findKthLargest(int[] nums, int k) {
shuffle(nums);
int l=0,r=nums.length-1;
k = nums.length-k;
while(l<=r){
int p = partition(nums,l,r);
if(p<k) l=p+1;
else if(p>k) r=p-1;
else return nums[p];
}
return -1;
}
int partition(int[] nums,int l,int r){
int i = l;
int base = nums[r];
for(int j=l;j<r;j++){
if(nums[j]<base){
swap(nums,i,j);
i++;
}
}
swap(nums,i,r);
return i;
}
void shuffle(int[] nums){
Random random = new Random();
int n = nums.length;
for(int i=0;i<n;i++){
int r = i+random.nextInt(n-i);
swap(nums,i,r);
}
}
void swap(int[] nums,int l,int r){
int tmp = nums[l];
nums[l] = nums[r];
nums[r] = tmp;
}
}
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
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
# 295. 数据流的中位数 (opens new window)
class MedianFinder {
PriorityQueue<Integer> large;
PriorityQueue<Integer> small;
public MedianFinder() {
this.large = new PriorityQueue<>();
this.small = new PriorityQueue<>((a,b)->{
return b-a;
});
}
public void addNum(int num) {
if(large.isEmpty() || num>=large.peek())
large.add(num);
else
small.add(num);
modifyTwoHeapSize();
}
public double findMedian() {
int largeSize = large.size();
int smallSize = small.size();
Integer largeHead = large.peek();
Integer smallHead = small.peek();
if(((largeSize+smallSize)&1)==0)
return (largeHead+smallHead)/2.0;
return largeSize>smallSize?largeHead:smallHead;
}
void modifyTwoHeapSize(){
if(large.size() == small.size()+2)
small.offer(large.poll());
if(small.size() == large.size()+2)
large.offer(small.poll());
}
}
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
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
# 347. 前 K 个高频元素 (opens new window)
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer,Integer> map = new HashMap<>();
for(int num:nums){
map.put(num,map.getOrDefault(num,0)+1);
}
PriorityQueue<Map.Entry<Integer,Integer>> pq = new PriorityQueue<>((o1,o2)->{
return o1.getValue().compareTo(o2.getValue());
});
for(Map.Entry<Integer,Integer> entry:map.entrySet()){
pq.offer(entry);
if(pq.size()>k){
pq.poll();
}
}
int[] ret = new int[k];
for(int i=k-1;i>=0;i--){
ret[i] = pq.poll().getKey();
}
return ret;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 373. 查找和最小的 K 对数字 (opens new window)
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
List<List<Integer>> res = new ArrayList<>();
PriorityQueue<int[]> pq = new PriorityQueue<>((a,b)->{
return (a[0]+a[1])-(b[0]+b[1]);
});
// 先将a[*]b[0]加入堆
for(int i=0;i<nums1.length;i++){
pq.offer(new int[]{nums1[i],nums2[0],0});
}
while(!pq.isEmpty() && k>0){
int[] cur = pq.poll();
k--;
int idx = cur[2]+1;
if(idx<nums2.length){
pq.add(new int[]{cur[0],nums2[idx],idx});
}
res.add(List.of(cur[0],cur[1]));
}
return res;
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 378. 有序矩阵中第 K 小的元素 (opens new window)
1
# 451. 根据字符出现频率排序 (opens new window)
class Solution {
public String frequencySort(String s) {
Map<Character,Integer> map = new HashMap<>();
for(char c:s.toCharArray()){
map.put(c,map.getOrDefault(c,0)+1);
}
PriorityQueue<Character> pq = new PriorityQueue<>((x,y)->{
return map.get(y)-map.get(x);
});
for(char c:map.keySet()){
pq.offer(c);
}
StringBuilder sb = new StringBuilder();
while(!pq.isEmpty()){
char k = pq.poll();
int v = map.get(k);
while(v-->0){
sb.append((char)k);
}
}
return sb.toString();
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 632. 最小区间 (opens new window)
# 659. 分割数组为连续子序列 (opens new window)
class Solution {
public boolean isPossible(int[] nums) {
var map = new HashMap<Integer,PriorityQueue<Integer>>();
for(int x:nums){
if(!map.containsKey(x)){
map.put(x,new PriorityQueue<Integer>());
}
//存在多个子序列以x−1结尾，将x加入其中最短的子序列
if(map.containsKey(x-1)){
int preLen = map.get(x-1).poll();
// 将子序列+1作为x结尾的子序列长度,x-1结尾的子序列减少一个，以x结尾的子序列增加一个
if(map.get(x-1).isEmpty()){
map.remove(x-1);
}
map.get(x).offer(preLen+1);
}else{
map.get(x).offer(1);
}
}
var entrySet = map.entrySet();
for(Map.Entry<Integer,PriorityQueue<Integer>> entry:entrySet){
PriorityQueue<Integer> que = entry.getValue();
if(que.peek()<3){
return false;
}
}
return true;
}
}
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
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