打算在这系列博客把hot100的题扫一遍，分模块来。
数组中的第K个最大元素 题目描述：
给定整数数组 nums 和整数 k，请返回数组中第 **k** 个最大的元素。
请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
你必须设计并实现时间复杂度为 O(n) 的算法解决此问题。
示例 1:
1
2
输入: [3,2,1,5,6,4], k = 2
输出: 5
示例 2:
1
2
输入: [3,2,3,1,2,4,5,5,6], k = 4
输出: 4
提示：
1 <= k <= nums.length <= 105-104 <= nums[i] <= 104
思路：
这题的o(n)挺难想到的，如果要考虑排序，最快的排序的时间复杂度也是o(nlogn)。因此参照了灵神的思路。
215. 数组中的第K个最大元素 - 力扣（LeetCode）
选第k大的元素的典型思路显然是堆，不过这题的时间复杂度是o(n)，堆排序也是做不到的，除非这题都是定制数据。
堆排序的maxHeapify是基于数组的典型建堆思路，需要掌握。
代码：
快选：
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
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
// 在子数组 [left, right] 中随机选择一个基准元素 pivot
// 根据 pivot 重新排列子数组 [left, right]
// 重新排列后，<= pivot 的元素都在 pivot 的左侧，>= pivot 的元素都在 pivot 的右侧
// 返回 pivot 在重新排列后的 nums 中的下标
// 特别地，如果子数组的所有元素都等于 pivot，我们会返回子数组的中心下标，避免退化
function partition(nums, left, right) {
// 1. 在子数组 [left, right] 中随机选择一个基准元素 pivot
const idx = left + Math.floor(Math.random() * (right - left + 1));
const pivot = nums[idx];
// 把 pivot 与子数组第一个元素交换，避免 pivot 干扰后续划分，从而简化实现逻辑
[nums[idx], nums[left]] = [nums[left], nums[idx]];
// 2. 相向双指针遍历子数组 [left + 1, right]
// 循环不变量：在循环过程中，子数组的数据分布始终如下图
// [ pivot | <=pivot | 尚未遍历 | >=pivot ]
// ^ ^ ^ ^
// left i j right
let i = left + 1, j = right;
while (true) {
while (i <= j && nums[i] < pivot) {
i++;
}
// 此时 nums[i] >= pivot
while (i <= j && nums[j] > pivot) {
j--;
}
// 此时 nums[j] <= pivot
if (i >= j) {
break;
}
// 维持循环不变量
[nums[i], nums[j]] = [nums[j], nums[i]];
i++;
j--;
}
// 循环结束后
// [ pivot | <=pivot | >=pivot ]
// ^ ^ ^ ^
// left j i right
// 3. 把 pivot 与 nums[j] 交换，完成划分（partition）
// 为什么与 j 交换？
// 如果与 i 交换，可能会出现 i = right + 1 的情况，已经下标越界了，无法交换
// 另一个原因是如果 nums[i] > pivot，交换会导致一个大于 pivot 的数出现在子数组最左边，不是有效划分
// 与 j 交换，即使 j = left，交换也不会出错
[nums[left], nums[j]] = [nums[j], nums[left]];
// 返回 pivot 的下标
return j;
}
var findKthLargest = function(nums, k) {
const n = nums.length;
const targetIndex = n - k; // 第 k 大元素在升序数组中的下标是 n - k
let left = 0, right = n - 1; // 闭区间
while (true) {
const i = partition(nums, left, right);
if (i === targetIndex) {
// 找到第 k 大元素
return nums[i];
}
if (i > targetIndex) {
// 第 k 大元素在 [left, i - 1] 中
right = i - 1;
} else {
// 第 k 大元素在 [i + 1, right] 中
left = i + 1;
}
}
};
堆排序，虽然o(nlogn)，但是定制题目，也能过：
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
var findKthLargest = function(nums, k) {
let heapSize = nums.length;
// 将以i为根的子树调整为大顶堆
// 逻辑：找i和其左右子中最大的，如果i不是最大的就交换，然后继续往下调整
function maxHeapify(i) {
const l = i * 2 + 1, r = i * 2 + 2; // 左子、右子下标
let largest = i; // 先假设自己最大
// 左子存在且比当前最大值大 → 更新largest
if (l < heapSize && nums[l] > nums[largest]) largest = l;
// 右子存在且比当前最大值大 → 更新largest
if (r < heapSize && nums[r] > nums[largest]) largest = r;
// 如果有子节点比父节点大，交换并继续往下调整
if (largest !== i) {
[nums[i], nums[largest]] = [nums[largest], nums[i]];
maxHeapify(largest); // 换下去的可能破坏子树，递归修复
}
}
// 建堆：从最后一个非叶子节点往根的方向，逐个执行maxHeapify
// heapSize/2-1 开始？因为后面的都是叶子节点，没有子树不需要调整
// 为什么从后往前？因为要先让底层子树满足堆性质，才能调整上层的父节点
for (let i = Math.floor(heapSize / 2) - 1; i >= 0; i--) {
maxHeapify(i);
}
// 弹出k-1个最大值，剩下的堆顶就是第k大
// 每次把堆顶（最大值）和末尾交换，heapSize--相当于"删除"它
for (let i = nums.length - 1; i >= nums.length - k + 1; i--) {
[nums[0], nums[i]] = [nums[i], nums[0]]; // 堆顶最大值换到末尾
heapSize--; // 缩小堆的范围，末尾元素"出堆"
maxHeapify(0); // 重新调整堆顶
}
// 堆顶就是第k大的元素
return nums[0];
};
前 K 个高频元素 题目描述：
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
示例 1：
输入：nums = [1,1,1,2,2,3], k = 2
输出：[1,2]
示例 2：
输入：nums = [1], k = 1
输出：[1]
示例 3：
输入：nums = [1,2,1,2,1,2,3,1,3,2], k = 2
输出：[1,2]
提示：
1 <= nums.length <= 105-104 <= nums[i] <= 104k的取值范围是[1, 数组中不相同的元素的个数]- 题目数据保证答案唯一，换句话说，数组中前
k个高频元素的集合是唯一的
进阶：你所设计算法的时间复杂度 必须 优于 O(n log n) ，其中 n 是数组大小。
思路：
最直接的思路是我们可以用map先遍历一遍，收集频次，然后再用堆来完成即可。虽然大根堆弹出k个也可完成，但用堆时我们考虑用小根堆会更优。因为大顶堆大小n，弹出k次 → O(n + k log n)；小顶堆大小k，直接留在里面就是答案 → O(n log k)。
和上一题对比大致如下。
| 第K大 | 前K高频 | |
|---|---|---|
| 堆类型 | 大顶堆，弹出k-1个 | 小顶堆，维护大小k |
| 堆大小 | n | k |
| 时间 | O(n + k log n) | O(n + n log k) |
进阶思路可以考虑用桶排序。347. 前 K 个高频元素 - 力扣（LeetCode）
计数排序和桶排序：
计数排序统计每个值出现几次，然后按顺序输出。
1
2
3
4
5
6
原数组: [3, 1, 2, 1, 3, 1]
计数: 下标 0 1 2 3
次数 0 3 1 2
输出: [1, 1, 1, 2, 3, 3]
直接用值当数组下标，统计次数，再按顺序展开。值域多大，计数数组就多大。
桶排序把值分到几个”桶”里，桶内再排序。
1
2
3
4
5
6
7
8
9
10
原数组: [29, 25, 3, 49, 9, 37, 21, 43]
按范围分桶:
桶0 (0-9): [3, 9]
桶1 (10-19): []
桶2 (20-29): [29, 25, 21]
桶3 (30-39): [37]
桶4 (40-49): [49, 43]
桶内排序后依次倒出
| 计数排序 | 桶排序 | |
|---|---|---|
| 桶的粒度 | 每个值一个桶 | 一个范围一个桶 |
| 桶内 | 不用排序（只有相同值） | 需要排序（值不同但相近） |
| 适用 | 值域小 | 值域大但分布均匀 |
代码：
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
47
48
49
50
51
var topKFrequent = function(nums, k) {
// 第1步：统计频次
const freq = new Map();
for (const num of nums) {
freq.set(num, (freq.get(num) || 0) + 1);
}
// 第2步：把频次和数值组成数组
const entries = [...freq.entries()]; // [[1,3], [2,2], [3,1]]
// 第3步：建小顶堆（按频次），维护大小为k
// 为什么用小顶堆？堆顶是最小的频次，新来的比它大就换掉它
const heap = [];
function siftUp(i) {
while (i > 0) {
const parent = Math.floor((i - 1) / 2);
if (entries[heap[i]][1] < entries[heap[parent]][1]) {
[heap[i], heap[parent]] = [heap[parent], heap[i]];
i = parent;
} else break;
}
}
function siftDown(i) {
const n = heap.length;
while (true) {
let smallest = i;
const l = 2 * i + 1, r = 2 * i + 2;
if (l < n && entries[heap[l]][1] < entries[heap[smallest]][1]) smallest = l;
if (r < n && entries[heap[r]][1] < entries[heap[smallest]][1]) smallest = r;
if (smallest !== i) {
[heap[i], heap[smallest]] = [heap[smallest], heap[i]];
i = smallest;
} else break;
}
}
for (let i = 0; i < entries.length; i++) {
if (heap.length < k) {
heap.push(i);
siftUp(heap.length - 1);
} else if (entries[i][1] > entries[heap[0]][1]) {
// 新元素频次比堆顶大，替换
heap[0] = i;
siftDown(0);
}
}
return heap.map(i => entries[i][0]);
};
可以看到小根堆的做法还是比较复杂的，而使用桶排序比较简单。
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
var topKFrequent = function(nums, k) {
const n = nums.length;
// 第1步：统计频次
const freq = new Map();
for (const num of nums) {
freq.set(num, (freq.get(num) || 0) + 1);
}
// 第2步：桶排序，下标=频次，值=该频次对应的所有数字
const buckets = new Array(n + 1).fill(null).map(() => []);
for (const [num, count] of freq) {
buckets[count].push(num);
}
// 第3步：从高频到低频收集k个
const ans = [];
for (let i = n; i >= 0 && ans.length < k; i--) {
for (const num of buckets[i]) { // forof会自动跳过空数组
ans.push(num);
if (ans.length === k) break;
}
}
return ans;
};