最小堆
最小堆是一种完全二叉树,特点是根节点比两个子节点都小(或者根节点比子节点都大)
过程
- 先找10000个数构建最小堆
- 依次遍历10亿个数,如果比最小堆的最小值大,则替换这个最小值,并重新构建最小堆
- 最后输入10000个值
- 时间复杂度 构建最小堆的复杂度为 logn,求出最大m个数会构建m次最小堆,时间复杂度为 m logm, 这里m为10000 进行n次时间复杂度为n,这里n为10亿,总时间复杂度为 n m logm,即10亿 10000 log 10000
其他算法
- 将十亿个数排序,找出最大值,但是占用空间比较大,做了很多无用功
- 分治法:将10亿个数分成10份,求出每份的前10000个数 ,然后在这个10 * 10000 个数中找出最大的10000个数
- hash去重复,将这10亿个数的Hash值进行比较,去除重复的