2020年12月25日 周五 天气晴 【不悲叹过去，不荒废现在，不惧怕未来】
本文目录
题目简介
剑指 Offer 40. 最小的k个数
经典TopK问题，雷同题目： LeetCode 215. 数组中的第K个最大元素（快排、堆排的应用）
1. 基于快排的快速选择（quick select）方法（减治）
快速选择（quick select）方法是快排的变形，通过递归执行partition操作，找出第k大元素的索引idx，然后返回[0,idx]即为最小的k个数。
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
// 处理特殊情况
if(k==arr.size() || arr.empty()) return arr;
if(k==0) return {};
int len = arr.size();
// 设置随机数种子
srand(time(0));
// 寻找第k大的元素索引idx，然后返回[0,idx]即为最小的k个数
return quickSelect(arr,0,len-1,k);
}
// 基于快排的选择方法（quick select）
vector<int> quickSelect(vector<int>& arr, int l, int r, int k){
int rand_idx = rand() % (r-l+1) + l;
swap(arr[l],arr[rand_idx]);
int idx = partition(arr,l,r);
// 返回最小的k个数
if(idx==k) return vector<int>(arr.begin(), arr.begin()+k);
else return idx<k?quickSelect(arr,idx+1,r,k):quickSelect(arr,l,idx-1,k);
}
// 分割操作（以中轴元素为基准，将数组分割成三部分，返回中轴元素索引）
int partition(vector<int>& arr, int l, int r){
int pivot = arr[l]; // 取第一个位置的元素作为中轴元素
// 右边主动接近左边，进行循环覆盖
while(l < r){
// 从右边寻找第一个大于 pivot 的数
while(l < r && arr[r] > pivot) --r;
// 找到后直接进行覆盖
arr[l] = arr[r];
// 从左边寻找第一个小于 pivot 的数
while(l < r && arr[l] <= pivot) ++l;
// 找到后直接进行覆盖
arr[r] = arr[l];
}
// 把pivot交换到中间，完成分割（因为是右边主动接近左边，所以这里是arr[l]）
arr[l] = pivot;
return l;
}
};
- 时间复杂度：由于引入了随机化，时间代价的期望是 O ( n ) O\left( {n} \right) O(n)
- 空间复杂度：递归调用的期望深度为 O ( l o g n ) O\left( {logn} \right) O(logn)
2. 最大堆（前k小）/ 最小堆（前k大）
本题也可以用最大堆：根据数组前 k 个元素建立一个大小为 k 的最大堆，然后遍历剩下的数组元素，与堆顶元素进行比较，动态调整堆中的元素，数组遍历结束后的堆中元素就是数组中前 k 小的元素。
2.1 手动实现最大堆
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
// 对数组中前k个元素建立最大堆
for(int i=k/2-1;i>=0;--i)
heapAdjustDown(arr,i,k);
// 从第k+1个元素开始遍历数组，将数组元素与堆顶元素进行比较
for(int i=k;i<arr.size();++i){
// 小于堆顶元素，则替换之
if(arr[i]<arr[0]){
swap(arr[0],arr[i]);
heapAdjustDown(arr,0,k);
}
}
// 遍历结束后，堆里的元素即为前k小元素
return vector<int>(arr.begin(), arr.begin()+k);
}
// 向下调整（常用于删除元素）
void heapAdjustDown(vector<int>& arrs, int parent, int curLen){
int curParent = arrs[parent];
int child = 2 * parent + 1; // 左孩子
while (child < curLen) { // 孩子不存在，跳出循环
if (child + 1 < curLen && arrs[child] < arrs[child + 1])
++child; // 右孩子的下标
if (curParent < arrs[child]) {
// 大值覆盖父结点，大值上浮，给小值腾出空间，类似简单插入排序(大值右移)
arrs[parent] = arrs[child];
parent = child;
// 迭代子树，因为如果子树中有比curParent大的，curParent还要继续下沉
child = 2 * parent + 1;
}
else break;
}
// 迭代结束，这时的p位置即为curParent应该在的位置
arrs[parent] = curParent;
}
};
2.2 使用STL中的优先队列 priority_queue
priority_queue 的底层实现就是堆，所以可以直接借助 priority_queue 解决问题。
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
vector<int> res(k,0);
if(k==0) return res;
priority_queue<int> q;
// 数组前k个元素入堆
for(int i=0;i<k;++i)
q.push(arr[i]);
// 根据数组中剩下元素更新堆
for(int i=k;i<arr.size();++i){
if(arr[i]<q.top()){
q.pop();
q.push(arr[i]);
}
}
// 取出堆内元素
for(int i=0;i<k;++i){
res[i] = q.top();
q.pop();
}
return res;
}
};
3. 红黑树
借助STL中的mutilset来实现，过程和使用priority_queue 实现很像。
class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
vector<int> res(k,0);
if(k==0) return res;
// 指定 multiset 从大到小排序
multiset<int,greater<int>> ms;
// 数组前k个元素加入multiset
for(int i=0;i<k;++i)
ms.insert(arr[i]);
// 根据数组中剩下元素更新multiset
for(int i=k;i<arr.size();++i){
if(arr[i]<*ms.begin()){
ms.erase(ms.begin());
ms.insert(arr[i]);
}
}
// 取出multiset中的元素
copy(ms.begin(), ms.end(), res.begin());
return res;
}
};
时间和空间复杂度同最大堆。
4. 总结（遇到海量数据时选择哪种方法？）
其实方法2和方法3都属于树的范畴，可以看作是一种方法，书上总结了这两种方法的优缺点，一定要牢记。
另外，海量数据的TopK问题可以参考这篇文章：【面试现场】如何在10亿数中找出前1000大的数
参考文献
《剑指offer 第二版》
https://leetcode-cn.com/problems/zui-xiao-de-kge-shu-lcof/solution/zui-xiao-de-kge-shu-by-leetcode-solution/
