网上看到的题目：一道腾讯面试题:从大量数字中取出 top 100

“最近有同事去腾讯面试,其中一个排序算法题:从1亿个数字中取出最大的100个. 我感觉用位图排序是比较合适的.位图排序的特点是用内存空间换取CPU时间.代码如下......”

发帖者的算法过于复杂，并且效率太低。实际上获取了前100个数字后，后一个数字如果比100个数字里最小的还大，就把那个最小的数字替换掉就完事了。1亿个数字，只需走一遍循环就可以了，总耗时不过2秒多点：

    public static void main(String[] args) {
        long start = System.currentTimeMillis();
        TreeSet<Long> set = new TreeSet<>();
        Random random = new Random();
        long randNum;
        for (int i = 0; i < 100; i++) {
            randNum = random.nextLong();
            set.add(randNum);
        }
        for (int i = 100; i < 100000000; i++) {
            randNum = random.nextLong();
            if (randNum > set.first()) {
                set.remove(set.first());
                set.add(randNum);
            }
        }
        System.out.println(set.toString());
        System.out.println("Time: " + (System.currentTimeMillis() - start) + "ms");
    }

题目没有指定数字是什么数字，就使用long型的了。内存消耗也没有什么压力。

i3的小机器耗时2秒多：

[9223351393230521254, 9223351574848852264, 9223351584238911326, 9223351949568176642, 9223352148090590140, 9223352251992930926, 9223352401392171214, 9223352614068359469, 9223352754399282720, 9223352933924302234, 9223352974375574012, 9223353247148312884, 9223353511498467611, 9223353751026683322, 9223353923712406388, 9223354258289213140, 9223354360681891187, 9223354628854910986, 9223354797419695852, 9223355191167563550, 9223355448215706820, 9223355983244858202, 9223356074559199013, 9223356217750592419, 9223356471638130744, 9223356508689914482, 9223356553872581402, 9223356615495170395, 9223356823359780850, 9223356905743944804, 9223357344468900917, 9223357534870218522, 9223357685138221826, 9223358233025313669, 9223359255406206996, 9223359289158476112, 9223359290806340327, 9223359575278925471, 9223360353531606534, 9223360597967587269, 9223361322055929499, 9223361324600166706, 9223361558426526310, 9223362244017906636, 9223362288188283876, 9223362306782799789, 9223362402976064781, 9223362627800992361, 9223362677334215953, 9223362757781061925, 9223362900108801319, 9223363163759943916, 9223363282819945960, 9223363630199811998, 9223363879233788921, 9223363958035201765, 9223364703135852644, 9223365162213010888, 9223365205337209896, 9223365284008855091, 9223365309094362429, 9223365369705184408, 9223365525081052814, 9223365669258572975, 9223365841587587837, 9223365978790625124, 9223366035653562095, 9223366050714297278, 9223366116738321743, 9223366144486352766, 9223366166300108699, 9223366540094096648, 9223366617934345443, 9223366639638863337, 9223367098049175116, 9223367115307195943, 9223367444876972455, 9223367685013368907, 9223367853623246015, 9223368015152635087, 9223368081002014200, 9223368178259833426, 9223368271674164382, 9223368459784625739, 9223368713354730897, 9223369111889552466, 9223369196642446831, 9223369385764089595, 9223369772251037347, 9223369800885160412, 9223369837122507349, 9223370168299364692, 9223370352062994273, 9223370476110389039, 9223370964598032331, 9223371102134478348, 9223371383800427535, 9223371825917730024, 9223371885841298523, 9223371903968821216]
Time: 2658ms

i5机器耗时2.3秒左右。

由于是单线程，提高不大。

这台电脑用时4秒多，差距相当大。

名花虽有主，我来松松土！

亚历（鸭梨）山大

春花那堪几度霜，秋月谁与共孤光；痴心若遇真情意，翩翩彩蝶化红妆。

人生有风险，入世需谨慎

我是个演员，一看见漂亮MM眼就圆……

,,,

这能代表一亿个数字吗？

回复 11 楼：

就是随机生成一亿个数字啊，可以代表的

但是一楼的算法有个问题，如果最大的100个数字有重复的，那么就只获取到了其中的一个值，其余的值就没法存了。所以可以考虑维护一个长度为100的数组，每次比较时获取一下最小值，如果大于最小值则替换。由于比较每个数字都要遍历一遍数组，所以效率只有1楼的1%，但是是个简单的可行方案了。另外可以考虑维护一个有序的树形结构，这样可能时间复杂度会低一些。由于数据结构没学好，所以还得补补课啊...

你帅呆了，酷毙了，简直无法比喻了，你头顶锅盖手拎白菜，总以为自己是东方不败，其实你是傻瓜二代!

我自横田向天笑，笑完我就去睡觉

好像很牛B的样子

被人抛弃？受人欺凌？无家可归？不要伤心，不要气馁，即使全世界都嫌弃你，至少还有我们，国营养猪场您温馨的家。

神看见你口渴，便创造了水；神看见你肚饿，便创造了米；神看见你寂寞，所以他创造了我。

祝你一路顺风，半路失踪；祝你笑口常开，笑死活该；祝你天天开心，两腿抽筋；祝你万事如意，处处碰壁。

佳节到, 送您一个月饼:第 一层财运;第二层幸运;第三层福运;第四层浪漫;中间夹层甜密！祝您天天好心情！