文章目录
方法一:
方法二:
方法三:
TopK问题,即寻找最大的K个数,这个问题非常常见,比如从1千万搜索记录中找出最热门的10个关键词.
方法一:
先排序,然后截取前k个数.
时间复杂度:O(n*logn)+O(k)=O(n*logn)。
方法二:
最小堆.
维护容量为k的最小堆.根据最小堆性质,堆顶一定是最小的,如果小于堆顶,则直接pass,如果大于堆顶,则替换掉堆顶,并heapify整理堆,其中heapify的时间复杂度是logk.
时间复杂度:O(k+(n-k)*logk)=O(n*logk)
方法三:
本文的主角.quick select算法.其实就......
阅读全文