60 亿,假设每个身高浮点数表示的话是 8 字节,大概 5 * 10^10 B = 50G 。如果内存放不下的话就放 50 个文件,每次对一个文件桶排序,取前 1000 个,最后对这 50 个文件共 50000 个数再桶排序一次
@picone 时间复杂度是对于输入来说的,在这个问题里,输入是 60 亿的身高数据,用一个大小为 1000 的堆进行排序取前 1000 大的数据,这个 1000 就是个常数,总的时间复杂度就是 O(n)。
用一个规模为 1000 的最小堆,然后遍历数据,如果比堆顶大,就替换堆顶,再调整一下堆结构。遍历完好,堆里面的数据就是前 1000 。 由于 1000 是固定的,每次维护最小堆的时间可以认为是一个常量 k ,这样一来,时间复杂度为 O(kN),等价与 O(N)。 这个方法适用于任何数据,从 N 个数据中取最大或最小的 n 个,只要 n 远小于 N 就行。