如何在海量数据中找出最大的k个数(Top K问题)

如何在拥有海量数据的数组N中找到最大的K条数据?或者如何找到频率出现最高的前k个数?这种问题就是Top K问题,有哪些方法可以解决呢,下面来分析一下。
1、全局排序 第一个自然想到的就是将所有的数据通过快排排好序,取前K个数,时间复杂度是O(nlogn),但是如果数据量特别大,是非常消耗内存的,而且明明只要前K个数,要把所有的数据都排序一遍也是很浪费的,有没有方法能局部排序呢?
2、局部排序 求最大的k个值,很自然的就想到冒泡排序了,每冒一次泡,拿到数组的最大值,时间复杂度是O(N*k),求10个数的话将数组扫描10次就拿到结果了。
3、堆排 用数组的前k个元素生成一个小顶堆,接着,从第k+1个元素开始扫描,和堆顶(堆中最小的元素)比较,如果被扫描的元素大于堆顶,则替换堆顶的元素,并调整堆,以保证堆内的k个元素,总是当前最大的k个元素。扫描完毕,堆中的元素就是最大的K个元素了。
时间复杂度:O(N*log(K))
4、随机选择排序 随机选择排序类似随机快排,每次partition都会确定一个元素的位置,比它大的数在它右边,比它小的数在它左边,如果p比目标下标小,就递归右子区间,否则递归左子区间,跟快排相比这样就可以把原来递归两个区间变成只递归一个区间,提高了时间效率,这是一个典型的减治算法,它的时间复杂度是O(n)。
【如何在海量数据中找出最大的k个数(Top K问题)】尽管它们是无序的,题目并没有要将这k个数排序,这样的话,只要在倒数第K个位置的元素分区完的时候,拿它右边的K的数,就是目标解了。

func FindKLargest(arr []int, index int) []int { arrLen := len(arr) return findKLargest(arr, 0, arrLen-1, arrLen-index) }func findKLargest(arr []int, start, end, index int) []int { p := partition(arr, start, end) if p == index { return arr[index:] } else if p < index { return findKLargest(arr, p+1, end, index) } return findKLargest(arr, start, p-1, index) }func partition(arr []int, start, end int) int { i := start pivot := arr[end] //比较值 for k := start; k <= end-1; k++ { if arr[k] < pivot { arr[k], arr[i] = arr[i], arr[k] i++ } } arr[end], arr[i] = arr[i], arr[end] return i }

    推荐阅读