top-k类问题
问题描述
从arr[1, n]这n个数中，找出最大的k个数，这就是经典的TopK问题。
1 直接排序
排序是最容易想到的方法，将n个数排序之后，取出最大的k个，即为所得：
sort(arr, 1, n); // 时间复杂度为O(n*lg(n))
return arr[1, k]; //全局的排序浪费大量时间，题中只需最大n个即可
2 局部排序
冒泡是一个很常见的排序方法，每冒一个泡，找出最大值，冒k个泡，就得到top-k：
sort(arr, 1, n); // 时间复杂度为O(n*lg(n))
return arr[1, k]; //全局的排序浪费大量时间，题中只需最大n个即可
3 堆
思路：只找到TopK，不排序TopK。先用前k个元素生成一个小顶堆，这个小顶堆用于存储，当前最大的k个元素。接着，从第k+1个元素开始扫描，和堆顶（堆中最小的元素）比较，如果被扫描的元素大于堆顶，则替换堆顶的元素，并调整堆，以保证堆内的k个元素，总是当前最大的k个元素。直到，扫描完所有n-k个元素，最终堆中的k个元素，就是猥琐求的TopK。
heap[k] = make_heap(arr[1, k]);
for(i=k+1 to n)
{
adjust_heap(heap[k], arr[i]); //时间复杂度：O(n*lg(k))
}
return heap[k];
堆，将冒泡的TopK排序优化为了TopK不排序，节省了计算资源，是求TopK的经典算法。
4 随机选择
随机选择算在是《算法导论》中一个经典的算法，其时间复杂度为O(n)，是一个线性复杂度的方法。不妨先了解前序知识：快速排序。
4.1 快速排序
快速排序的核心为分治法。
4.1.1 分治法
分治法（Divide & Conquer），指把一个大的问题，转化为若干个子问题（Divide），每个子问题“都”解决，大的问题便随之解决（Conquer）。这里的关键词是“都”。从伪代码里可以看到，快速排序递归时，先通过partition把数组分隔为两个部分，两个部分“都”要再次递归。
void quick_sort(int[]arr, int low, int high)
{
if (low >= high) return;
int i = partition(arr, low, high); // the key
quick_sort(arr, low, i - 1);
quick_sort(arr, i + 1, high);
}
4.1.2 减治法
分治法有一个特例，叫减治法（Reduce & Conquer）。把一个大的问题，转化为若干个子问题（Reduce），这些子问题中“只”解决一个，大的问题便随之解决（Conquer）。这里的关键词是“只”。
二分查找binary_search，BS，是一个典型的运用减治法思想的算法，其伪代码是：
int BS(int[]arr, int low, int high, int target)
{
if (low > high) return -1;
int mid = low + ((high - low) >> 1);
if (arr[mid] == target) return mid;
else if (arr[mid] > target)
return BS(arr, low, mid - 1, target);
else
return BS(arr, mid + 1, high, target);
}
从伪代码可以看到，二分查找，一个大的问题，可以用一个mid元素，分成左半区，右半区两个子问题。而左右两个子问题，只需要解决其中一个，递归一次，就能够解决二分查找全局的问题。
可以发现快速排序时间复杂度为：O(n*lg(n))，而二分查找为：O(lg(n))。
4.1.3 partition
顾名思义，partition会把整体分为两个部分。更具体的，会用数组arr中的一个元素（默认是第一个元素t=arr[low]）为划分依据，将数据arr[low, high]划分成左右两个子数组：左边比t大，右边比t小，中间位置i为划分元素。
把整个数组扫一遍后partition的时间复杂度为O(n)。
在解决top-k类问题时，可以用大partition的思想：top-k是希望求出arr[1,n]中最大的k个数，那如果找到了第k大的数，做一次partition，不就一次性找到最大的k个数了么？问题变成了arr[1, n]中找到第k大的数。
再回过头来看看第一次partition，划分之后，i = partition(arr, 1, n)：
-
如果i大于k，则说明arr[i]左边的元素都大于k，于是只递归arr[1, i-1]里第k大的元素即可。
-
如果i小于k，则说明说明第k大的元素在arr[i]的右边，于是只递归arr[i+1, n]里第k-i大的元素即可。
这就是随机选择算法(randomized_select，RS)，其伪代码如下：
int RS(int[]arr, int low, int high, int k)
{
if (low == high) return arr[low];
int i = partition(arr, low, high);
int t = i - low; // 计算左半部分元素个数
if (t >= k)
return RS(arr, low, i - 1, k); // 左半部分查找第k小元素
else
return RS(arr, i + 1, high, k - t); // 右半部分查找第(k-t)小元素
}
这是一个典型的减治算法，递归内的两个分支，最终只会执行一个，它的时间复杂度是O(n)。
整体的代码如下：
#include<iostream>
using namespace std;
int q[10000] ,n ,k ;
int quickSort(int *a ,int l ,int r ,int k)
{
if(l >= r) return 0 ;
int i = l - 1 ,j = r + 1 ,m = a[l + j >> 1] ;
while(i < j)
{
do j -- ;while(a[j] > m);
do i ++ ;while(a[i] < m);
if(i < j) swap(a[i],a[j]);
}
int t = i - l ;
if(t >= k) return quickSort(a ,l ,j ,k );
else return quickSort(a ,j + 1 ,r ,k );
}
int main()
{
cin >> n >> k;
for(int i = 0 ;i < n ;i ++) cin >> q[i];
quickSort(q ,0 ,n - 1 ,k );
for(int i = n - k ;i < n ;i ++) cout << q[i] << " " ;
return 0;
}
//input:
10 2
9 3 4 8 7 1 10 5 2 6
//output:
10 9
确定其中第k个最大值的解法：
- 选择排序或交互排序，K次选择后即可得到第k大的数。总的时间复杂度为O(nk).
- 用O(4n)的方法对原数组建最大堆，然后pop出k次即可。时间复杂度为O(4n + k*logn).
- 利用hash保存数组中元素q[i]出现的次数，利用计数排序的思想，线性从大到小扫描过程中，前面有k-1个数则为第k大数，平均情况下时间复杂度O(n).
- STL中可以用nth_element求得类似的第n大的数（由谓词决定），还可以用partial_sort对区间进行部分排序，得到类似前k大的数（由谓词决定），
总结
top-k类问题的思路变化：
- 全局排序，O(n*lg(n))；
- 局部排序，只排序TopK个数，O(n*k)；
- 堆，TopK个数也不排序了，O(n*lg(k))；
- 分治法，每个分支“都要”递归，例如：快速排序，O(n*lg(n))；
- 减治法，“只要”递归一个分支，例如：二分查找O(lg(n))，随机选择O(n)；
- TopK的另一个解法：随机选择+partition。
本文为学习随笔，附上原文链接 一次搞透，面试中的TopK问题!，寻找第K大的数的方法总结
原文地址：https://blog.csdn.net/2301_80010036/article/details/143610180
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！