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 keyquick_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小元素elsereturn 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大的数（由谓词决定），