Top K
Top K
Overview
主要的思路是O(nlogn)的PriorityQueue / Sort 和 Average O(n)的Quick Select. 还有一个常见的是关于频率，对于Java需要注意一下Override Comparator的写法。
Problems
- Kth Largest Element in an Array
- Kth Smallest Element in a BST
- Top K Frequent Elements
- Top K Frequent Words
- Kth Largest Element in a Stream
- Sort Characters By Frequency
- Find K Closest Elements
- Method 1: 直接两次排序
- Method 2: 先Binary Search找到target最近的位置，然后two points向外扩张
- Reorganize String
- Rearrange String k Distance Apart
- 和上面本质上一个意思，用greedy，先统计频率，然后由高到低构建结果
- Maximum Frequency Stack
- K Closest Points to Origin
- 如果需求的前K个元素是无序的，我们仍然可以使用quickselect
- Kth Smallest Element in a Sorted Matrix
- Follow up may focus on how to compare the time complexity between K and N (num of rows)
Quick Select
1private int quickSelect(int left, int right){
2 int index = partition(left, right);
3 if (index == k - 1){
4 return nums[index];
5 }else if (index > k - 1){
6 return quickSelect(left, index - 1);
7 }else{
8 return quickSelect(index + 1, right);
9 }
10}
11
12private int partition(int left, int right){
13 //if (left > right) return -1;
14 if (left == right) return left;
15 Random rand = new Random();
16 int pivot_index = left + rand.nextInt(right - left);
17 swap(pivot_index, right);
18 int pivot = nums[right];
19 int i = left;
20 for (int j = left; j < right; j++){
21 if (pivot < nums[j]){
22 swap(j, i);
23 i++;
24 }
25 }
26 swap(i, right);
27 return i;
28}
29
30private void swap(int i, int j){
31 int tmp = nums[i];
32 nums[i] = nums[j];
33 nums[j] = tmp;
34}
如果是从大到小，在pivot和nums[j]比较的时候，我们需要的是找到pivot的正确位置顺便把比pivot大的放到前面，而i是负责最后的位置，所以pivot < nums[j] 交换i, j