共计 1104 个字符,预计需要花费 3 分钟才能阅读完成。
如何在领有海量数据的数组 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 个数排序,这样的话,只有在倒数第 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
}
正文完