@picone 一般是像你这么算的,每次都是和堆顶比较,比堆顶大的才删除堆顶,再插入;如果比堆顶小,直接就 pass 了,算法复杂度就是 O(nlogk);但是身高应该是符合正态分布的,前 1000 名身高可能只占百分之零点零几,甚至更少,60 亿数据中,基本上没多少次插入
受 6 楼启发,480 个桶,先取 1000 个放入各自的桶内,然后淘汰掉数量不为 0 的最小的桶后面的所有桶,初始化一个计数器,初始值为最小的桶内令牌的数量。后面再次取数时,如果小于最小的桶,直接丢弃(节省哈希时间),如果这个数是此时场上最小的桶,则计数器加 1 ,如果不是最小的桶,计数器-1 ,当计数器为 0 时,丢弃最小的桶,重新排序找到新的最小的桶,计数器设置为新的最小的桶内令牌数量。重复该操作,直到遍历完 60 亿数,此时剩下的就是最大的 1000 个(数量可能会超过 1000 ,因为最小的桶可能有很多相同的值)。
也不考虑 O(n),我们的期望是 [一轮遍历+尽可能少的空间] 达到筛选目的。 在现实中处理此类问题需要数据清洗并建模,简单地,我们需要预估身高分布,比如是全随机分布还是正态分布? 无论是哪一种,我们都能估算出一个合适的身高范围,如果用桶,这个范围会使桶的数量大大减少。
分别创建:List ,最大变量 A ,最小变量 B ,遍历 txt 数据时每次和最大变量 A 和最小变量 B 对比,将最大数据计入即可,然后加入 List ,让 List 始终保持 1000 个以内即可,遍历完成后对 List 快速排序既可以,非常简答