TOP K问题的算法分析与实现
TOP K问题的算法分析与实现
本文是完全参考这篇博文《Top k算法分析》的思路来讲述的，为了自我锻炼，对其中的一些细节知识进行了补充，以及对于实现代码进行了完整化。
问题描述
- 经典的top k问题
给定一个含有n个整数的数组，要找出其中前k个（k≤n）最大的元素。
随着数据结构的丰富以及应用的场景的增多，很多top k问题的外表会裹上或多或少的伪装。
- 示例
本质上，top k的问题是想要对一组相同类型的数据按照某种标准（键值）进行比较排序，找出其中前k个比较结果最大的数据元素。
注：以下问题的讨论以及代码的实现都是基于最经典的top k问题来实现的。
问题解决
整个问题的解决肯定是离不开排序关系的，优化的线路可以从整体排序到局部排序再到分治和减治的应用。
以排序为主线的算法与优化
全局排序------O(nlgn)
思路：（最简单粗暴的一种方式）对给定的数据进行一个降序排序，那么前k个元素自然就是需要的前k个最大的元素。
#include<bits/stdc++.h>
using namespace std;
void overall_sort(vector<int> rec,int n,int k){
sort(rec.begin(),rec.end(),greater<int>());//进行降序排序，具体看问题需求
for(int i = 0;i<k;i++)
cout<<rec[i]<<endl;
}
int main(){
int n,k;
cin>>n>>k;
//处理输入数据
vector<int> rec;
for(int i = 0;i<n;i++){
int t;
cin>>t;
rec.push_back(t);
}
overall_sort(rec,n,k);
return 0;
}
对于C++中调用的sort函数，读者可以用归并或者快排（要先shuffle一下）来实现。
注：有关归并算法的相关讲解可以参考这篇博文《归并排序算法的实现与分析》
对于数组这样的存储结构，排好序后的前k个元素的读取都是随机的了，所以算法的核心复杂度主要画在对n个元素进行排序上。
局部排序-----O(n*k)
思路：既然只要找前k个最大的元素，那么就只对前k个元素进行排序（只要找到前k个最大的元素即可）。
此时可以回顾一下我们常用的排序算法（冒泡，选择，插入，快排，归并）等，每一次排序可以确定最终结果某一个位置的元素的算法有：冒泡，选择，快排。
冒泡和选择都是在第k轮就可以确定前k个元素，快排是每一轮会确定切分位的某一个元素（元素的位置上理论上来说是随机的）
所以我们使用选择排序或者冒泡排序都可以进行局部排序。
#include<bits/stdc++.h>
using namespace std;
void bubble_operation(vector<int> &a,int b){
int n = a.size();
for(int i = 0;i<n-b;i++){
if(a[i]>a[i+1]){
a[i] ^= a[i+1];
a[i+1] ^= a[i];
a[i] ^= a[i+1];
}
}
}
void part_sort(vector<int> rec,int n,int k){
for(int i = 1;i<=k;i++){
bubble_operation(rec,i);
cout<<rec[n-i]<<endl;
}
}
int main(){
int n,k;
cin>>n>>k;
//处理输入数据
vector<int> rec;
for(int i = 0;i<n;i++){
int t;
cin>>t;
rec.push_back(t);
}
part_sort(rec,n,k);
return 0;
}
其中bubble_operation就是冒泡排序一次扫描的操作，故每一次调用bubble的操作的复杂度都是O(n);
p.s. bubble操作需要传入一个整型参数，以便告诉程序这是冒泡排序的第几轮排序。
第i次调用bubble都可以确定第i大的数字（从数组的最末端开始存放），故只需要调用k次就可以得到前k个最大的数字。
局部不排序——借用堆的数据结构—O(n*lgk)
思路：【具体要看题目需求】有时候题目只要给出含有前k个元素的数据集合，这k个元素之间不区分顺序。
那么可以借助最大堆来存储这k个元素。
堆的知识补充
1. 堆与堆排序
（1）堆的定义
（2）堆排序
堆排序是一种树形选择排序方法。
其特点：在排序过程中，将L[1…n]看成是一棵完全二叉树的顺序存储结构，利用完全二叉树中双亲节点和孩子节点的内在关系，在当前无序区中选择关键字最大（或最小）的元素。
（3）堆有序
当一棵二叉树的每个节点都大于等于它的两个子节点时，它被称为堆有序。
2. 堆的有序化
（1）定义
堆的操作会首先进行一些简单的改动，打破堆的状态，然后再遍历堆并按照要求将堆的状态恢复。
这一过程就称作为堆的有序化。
在对堆进行有序化的过程中会遇到两种情况——
①当某个节点的优先级上升（或在堆底加入一个新的元素），需要从下至上恢复堆的顺序——上浮（swim）
②当某个节点的优先级下降（例如根节点被替换为一个更小的元素），需要从上至下地恢复堆的顺序——下沉（sink）
（2）由下至上的堆有序化——swim
原因和过程：
当某个节点变得比它的父节点更大，从而打破了堆的有序状态，就需要通过交换它和它的父节点来修复堆。
交换后，这个节点比它的两个子节点都大，且这个节点仍然可能比它现在的父节点还要大。
我们可以一遍遍地用同样的办法来恢复秩序，将这个节点不断向上移动直到我们遇到了一个更大的父节点。
机制：
位置k的节点的父节点位置是(k/2)取下整。
void swim(int k,int arr[]){
while(k > 1 && arr[k/2]<arr[k]){
exch(arr,k/2,k);//此处是抽象方法
k = k / 2;
}
}
swim()中的循环保证了只有位置k上的节点大于它的父节点时堆的有序状态才会被打破。因此只要该节点不再大于它的父节点，堆的有序状态就得到了恢复。
（3）由上至下的堆有序化——sink
原因和过程：
当某个节点变得比它的两个子节点或其中之一更小，从而打破了堆的有序状态，就需要通过交换它和它的两个子节点中的较大者来进行恢复。
交换后，可能在它的新的子节点处继续打破堆的有序状态，因此我们需要不断地用相同的方式将其恢复。将节点向下移动直到它的子节点都比它更小或者达到了堆的底部。
机制：
位置k的节点的子节点分别位于2k和2k+1
void sink(int k,int arr[]){
//N为数组arr的总长度
while(2*l <= N){
int j = 2 *k;
if(j < N && arr[j]<arr[j+1])//确定当前节点的较小的那个子节点
j++;
if(arr[k]>=arr[j])
break;//如果该节点并不比其子节点小，就说明堆的有序状态并没有被破坏
exch(arr,k,j);
k = j;
}
}
（4）堆的其他操作
①插入元素
插入元素操作是构造堆的重要步骤。
将需要插入的新元素放在数组末尾，增加堆的大小并让这个新元素上浮到合适的位置上。
②删除最大元素
删除元素在实现堆排序中也尤为重要
从数组顶端删去当前最大元素，并将数组的最后一个元素放到数组的顶端，减小堆的大小并让这个新的堆顶元素下沉到合适的位置上。
利用小顶堆解决Top K问题
思路：只找到TOP k ，不对Top k进行排序。
先利用数组中的前k个元素构造一个小顶堆，这个小顶堆中存储的就是当前最大的k个元素。
接着，从第k+1个元素进行扫描，和小顶堆中的堆顶（前k个最大元素中最小的那一个），若被扫描的元素大于堆顶元素，就替换堆顶的元素，并进行后续的调整，以保证堆内的k各元素总是当前最大的k个元素。
当扫描完剩下的n-k个元素，此时小顶堆中保存的元素就是所要找的元素。
#include<bits/stdc++.h>
using namespace std;
vector<int> heap;
void swim(int a){
while(a >1 && heap[a/2]>heap[a]){
int t = heap[a/2];
heap[a/2] = heap[a];
heap[a] = t;
a /= 2;
}
}
void sink(int a,int k){
while(2*a <= k){
int j = 2*a;
if(j<k&&heap[j]>heap[j+1])
j++;
if(heap[a]<=heap[j])
break;
int t = heap[a];
heap[a] = heap[j];
heap[j] = t;
a = j;
}
}
void make_heap(vector<int> a,int b){
int pointer = 0;//维护的当前堆的指针
for(int i = 0;i<b;i++){
pointer++;
heap.push_back(a[i]);
swim(pointer);
}
}
void use_heap_sort(vector<int> arr,int n,int k){
make_heap(arr,k);
for(int i = k;i<n;i++){
if(arr[i]>heap[1]){
heap[1] = arr[i];
sink(1,k);
}
}
for(int i = 1;i<=k;i++)
cout<<heap[i]<<endl;
}
int main(){
heap.push_back(-100);
int n,k;
cin>>n>>k;
//处理输入数据
vector<int> rec;
for(int i = 0;i<n;i++){
int t;
cin>>t;
rec.push_back(t);
}
use_heap_sort(rec,n,k);
return 0;
}
时间复杂度分析：
只需要从头到尾将n个元素都扫描一遍即可；扫描前k个元素是为了初始化一个小顶堆，扫描后面n-k个元素是为了保证小顶堆中存储的一直都是数组中前k个最大的元素。
考虑最坏的情况，假设扫描每一个元素都需要进入到堆中进行动态调整。因为我们是借助二叉树来实现堆的数据结构，堆的相关操作的复杂度和堆深有关。
故整体时间复杂度为n*lgK
以分（减）治为主线的解决思路
快速排序——分治/递归
在前面讲解全局排序的时候，我提到过C++模板库中的sort（）函数，读者可以通过自己实现快排来实现，快排常见的实现方式是自上而下的递归方式，其本质蕴含的算法思想就是分治。
后续如果有时间会再单独做一次有关快排的博文，以下只简要贴出快排的逻辑伪代码。
void quick_sort(int[]arr, int low, inthigh){
if(low== high) return;
int i = partition(arr, low, high);
quick_sort(arr, low, i-1);
quick_sort(arr, i+1, high);
}
随机选择——减治法
1. 分治与减治
分治法
把一个大的问题，转化成若干个规模较小的子问题，不断划分削减子问题的规模，直到所有的子问题都能够得到解决时，大问题随之得到解决。
减治法
可以把减治法看做是分治法的一个特例。
把一个大的问题，转化成若干个子问题，这些子问题只解决其中一个子问题，大问题就能够得到解决。
读者可以通过体会归并排序和二分查找的关系来理解所谓分治和减治。
2. 随机选择算法及实现
（1）思想
在讲述随机选择之前，还是先将目光放到快排算法中；根据下图，可以将快排划分成两个模块，其一是对数组进行切分（partition），其二就是递归地对切分元素的左右两部分进行排序。
在快排中最重要的就是切分操作，它的实现是通过维护两个指针，依次比较两个指针指向的元素和选定的切分元素的大小关系，使得最后在切分元素右侧的元素值都大于或等于切分元素，左侧则反之。
当然，切分元素的左侧值大于右侧值亦或是反之，可以在具体实现时根据题目需要进行变动。
比如我们在TOPK 问题中要找前k个最大的元素，就需要对数组进行逆序排序，那么就应该使得切分元素左侧的值均大于其右侧的值。
那么将partiition的思想放到TOP K问题中，我们进行了一次切分i = partition(arr, 1, n)之后
- 若i小于k，说明我们只能保证前i个元素是当前最大的，但是还需要从右侧找出剩下的k-i个元素，需要递归arr[i+1,n]里第k-i大的元素。
- 若i大于k，就说明我们已经找出了前i个最大的元素，但是在左侧还混有i-k个是我们不需要的，需要递归arr[1,i-1]里第k大的元素。
（2）代码实现
#include<bits/stdc++.h>
using namespace std;
vector<int> heap;
int RS(vector<int> arr,int low,int high,int k){
if(low == high)
return arr[low];
int i = partition(arr,low,high);//本节代码没有对partition进行实现
int t = i - low;
if(t >= k)
return RS(arr,low,i-1,k);
else
return RS(arr,i+1,high,k-i);
}
int main(){
int n,k;
cin>>n>>k;
//处理输入数据
vector<int> rec;
for(int i = 0;i<n;i++){
int t;
cin>>t;
rec.push_back(t);
}
RS(rec,0,n-1,k);
for(int i = 0;i<k;i++)
cout<<rec[i]<<endl;
return 0;
}
Leetcode- 973 不同题解实现
又一次在每日一题中碰到这道题，看到评论中有人晒出了快排的减治算法版本，才想起来这就是TOP K问题。
于是翻到这篇博文，再重新修订一下~
备注：敲代码很差的本渣渣，代码都是照着评论区的大佬打出来的~自己敲一遍加记录一遍记忆更深刻。
题目描述
Leetcode -973 最接近原点的K个点
我们有一个由平面上的点组成的列表 points。需要从中找出 K 个距离原点 (0, 0) 最近的点。
（这里，平面上两点之间的距离是欧几里德距离。）
你可以按任何顺序返回答案。除了点坐标的顺序之外，答案确保是唯一的。
示例如下：
题解实现
1. 全局排序
因为有封装好的stl的排序模板sort，只需要按照问题的逻辑重写比较函数即可。
class Solution {
public:
struct cmp{
bool operator()(vector<int> &a,vector<int> &b){
return a[0]*a[0]+a[1]*a[1]<b[0]*b[0]+b[1]*b[1];
}
};
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
vector<vector<int> > res;
sort(points.begin(),points.end(),cmp());
res.assign(points.begin(),points.begin()+K);
return res;
}
};
2. 优先队列实现堆结构
可以重写优先队列的比较逻辑，或者直接把每个点关于原点的距离放进堆中，这个过程需要把点的下标也一起放进去，因为堆是动态变化的。
class Solution {//官方题解
public:
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
priority_queue<pair<int, int>> q;
for (int i = 0; i < K; ++i) {
q.emplace(points[i][0] * points[i][0] + points[i][1] * points[i][1], i);
}
int n = points.size();
for (int i = K; i < n; ++i) {
int dist = points[i][0] * points[i][0] + points[i][1] * points[i][1];
if (dist < q.top().first) {
q.pop();
q.emplace(dist, i);
}
}
vector<vector<int>> ans;
while (!q.empty()) {
ans.push_back(points[q.top().second]);
q.pop();
}
return ans;
}
};
3. 快排减治
因为快排的partition函数返回了下标m，就说明前m个元素都不会大于后n-m个（假设共有n个元素）元素，换句话说，每一次partition后都找到了整个数组的前m个小的元素。
注：前m个元素之间是乱序的，本题可以按任何顺序返回答案，符合要求。
class Solution {
public:
int partition(vector<vector<int> > &points,vector<int> &dist,int left,int right){
auto val = points[left];
int key = dist[left];//按照dist中的值对points和dist进行重排划分
while(left < right){
while(left < right && dist[right]>=key) right--;//找到第一个小于划分元素的右端值
points[left] = points[right];
dist[left] = dist[right];
while(left<right && dist[left]<=key) left++;
points[right] = points[left];
dist[right] = dist[left];
}
points[left] = val;
dist[left] = key;
return left;//返回的是小于dist[left]的前left个元素
}
vector<vector<int>> kClosest(vector<vector<int>>& points, int K) {
if(K >= points.size() )
return points;
vector<int> dist(points.size());
for(int i = 0;i < points.size();i++){
int x = points[i][0],y = points[i][1];
dist[i] = x * x + y * y;
}
int left = 0,right = points.size()-1;
while(left!=K){
int mid = partition(points,dist,left,right);
if(mid == K)
break;
else if(mid < K)
left = mid + 1;
else right = mid - 1;
}
vector<vector<int> > res;
res.assign(points.begin(),points.begin()+K);
return res;
}
};