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个的问题其实并不需要完全排序，只需要粗略排，比如优先队列中头部元素永远是最大或者最小的，那么可能多余的操作就不必要了。堆的本质还是一个二叉树，父节点永远比子节点大（小）。