从N个数中找出最大的K个数

  1. 排序 O(NlogN)
  2. 冒泡排序 O(N*K)
  3. 小根堆 O(NlogK)
    • 如果求最大k个数就用小根堆，如果求最小k个数就用大根堆
    • 虽然不是最快的，但是却是最好的方式，因为可以处理海量数据
  4. 快排 O(N)
    • 首先要把求最大的K个数转为求第K大的数。

海量数据中，找出出现频率最大的k个数

  1. 首先统计每个数字出现的频率，可以用HashMap来完成；如果量特别大，大到一台机器不足以完成频率计算的过程的话，可以用MapReduce框架（利用一个映射对数据进行分类，而且包含了去重的过程！）。
  2. topK