378. Kth Smallest Element in a Sorted Matrix
题目大意是给定一个n×n的矩阵，每行每列都是从小到大的顺序，找出矩阵中第k小的元素。
利用优先队列的性质，将每个矩阵中的元素放入，第k小就是第n×n-k+1大，模板代码来一遍，然后就是O(n²)的时间复杂度。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public int kthSmallest(int[][] matrix, int k) {
int n = matrix.length;
PriorityQueue<Integer> q = new PriorityQueue<>();
for(int i=0; i<n; i++) {
for(int j=0; j<n; j++) {
q.add(matrix[i][j]);
if(q.size() > n*n - k + 1) {
q.poll();
}
}
}
return q.peek();
}
}
|
这种解法很明显漏掉了每行每列排序的性质，所以即便没排序的矩阵都是ok的。那么这两个关键性质该怎么用，discuss里有人找到了论文
https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/discuss/85170/O(n)-from-paper.-Yes-O(rows).
只能先做个笔记，希望有人讨论讨论。
215. Kth Largest Element in an Array
题目大意是找到数组中第k大的元素，几乎和703的题目一样，还是模板代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
PriorityQueue<Integer> q = new PriorityQueue<>();
for(int i=0; i<n; i++) {
q.add(nums[i]);
if(q.size() > k) {
q.poll();
}
}
return q.peek();
}
}
|
但是这一题是一个数组，那么在一个有序的数组中找第几大不是很容易的事吗？那么我们就可以排序再找。
1
2
3
4
5
6
7
| class Solution {
public int findKthLargest(int[] nums, int k) {
int n = nums.length;
Arrays.sort(nums);
return nums[n-k];
}
}
|
最后看到一个根据快速排序思路的解法，觉得也挺好的，顺路再理解一遍快排的算法。在快排中，第一步是先选取一个基准数，一般都以第一个作为基准数，然后从两头开始都和这个基准数比较。因为是找第几大，那么就从大到小排序，把所有比基准数大的放其左侧，比基准数小的放其右边，当这一步操作完成后，基准数就该被排序好了，那么此时只要比较它的下标和k-1（第k大在数组中就是第k-1）是否一致，如果一致那么就是要找的，说明最好的情况只需要O(n)的时间复杂度。如果不一致那么只需要在一侧再去找，这就又有了二分的思想。
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
| class Solution {
public int findKthLargest(int[] nums, int k) {
int low = 0;
int high = nums.length - 1;
while (low < high) {
int j = partition(nums, low, high);
if (j < k-1) {
low = j + 1;
} else if (j > k-1) {
high = j - 1;
} else {
break;
}
}
return nums[k-1];
}
public int partition(int[] a, int low, int high) {
int i = low;
int j = high+1;
while(i < j) {
while(a[++i]>a[low] && i < high);
while(a[--j]<a[low] && j > 0);
if(i<j) swap(a, i, j);
}
swap(a, low, j);
return j;
}
public void swap(int[] a, int i, int j) {
int temp = a[j];
a[j] = a[i];
a[i] = temp;
}
}
|
692. Top K Frequent Words
题目大意是找到前k个出现频率最高的单词，按照频率从大到小排，如果频率相同就按单词字母从小到大的顺序，小字母开头的在前。
继续利用HashMap+优先队列，继续模板代码。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
| class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String, Integer> map = new HashMap<>();
for(String w : words) {
map.put(w, map.getOrDefault(w, 0) + 1);
}
PriorityQueue<String> q = new PriorityQueue<>(
(a, b)-> {if(map.get(a) == map.get(b)) return b.compareTo(a);
else return map.get(a) - map.get(b);});
for(String w : map.keySet()) {
q.add(w);
if(q.size() > k) {
q.poll();
}
}
List<String> res = new ArrayList<>();
while(!q.isEmpty()) {
res.add(q.poll());
}
Collections.reverse(res);
return res;
}
}
|
总结
做了这么多前k个问题的题目，对最小堆（优先队列）有了一定的认识，其实前k个题目都可以转成排序的问题来做，我个人的理解是转成排序的话就是完全排序，每个元素都是排好的，那么问题都好解决，就比如前k个的问题其实并不需要完全排序，只需要粗略排，比如优先队列中头部元素永远是最大或者最小的，那么可能多余的操作就不必要了。堆的本质还是一个二叉树，父节点永远比子节点大（小）。