【面试现场】如何在10亿数中找出前1000大的数

小史是一个应届生，虽然学的是电子专业，但是自己业余时间看了很多互联网与编程方面的书，一心想进BAT互联网公司。

之前小史在BAT三家的面试中已经挂了两家，今天小史去了BAT中的最后一家面试了。

简单的自我介绍后，面试官给了小史一个问题。

【面试现场】

题目：如何在10亿数中找出前1000大的数？

小史：我可以用分治法，这有点类似快排中partition的操作。随机选一个数t，然后对整个数组进行partition，会得到两部分，前一部分的数都大于t，后一部分的数都小于t。

小史：如果说前一部分总数大于1000个，那就继续在前一部分进行partition寻找。如果前一部分的数小于1000个，那就在后一部分再进行partition，寻找剩下的数。

小史：首先，partition的过程，时间是o(n)。我们在进行第一次partition的时候需要花费n，第二次partition的时候，数据量减半了，所以只要花费n/2，同理第三次的时候只要花费n/4，以此类推。而n+n/2+n/4+...显然是小于2n的，所以这个方法的渐进时间只有o(n)

（注：这里的时间复杂度计算只是简化计算版，真正严谨的数学证明可以参考算法导论相关分析。）

半分钟过去了。

小史一时慌了神。

他回忆起了之前吕老师给他讲解bitmap时的一些细节。突然有了一个想法。

小史在纸上画了画。

理解了算法之后，小史的代码写起来也是非常快，不一会儿就写好了：

TopN.java

/**
 * @author xiaoshi on 2018/10/14.
 */
public class TopN {

    // 父节点
    private int parent(int n) {
        return (n - 1) / 2;
    }

    // 左孩子
    private int left(int n) {
        return 2 * n + 1;
    }

    // 右孩子
    private int right(int n) {
        return 2 * n + 2;
    }

    // 构建堆
    private void buildHeap(int n, int[] data) {
        for(int i = 1; i < n; i++) {
            int t = i;
            // 调整堆
            while(t != 0 && data[parent(t)] > data[t]) {
                int temp = data[t];
                data[t] = data[parent(t)];
                data[parent(t)] = temp;
                t = parent(t);
            }
        }
    }

    // 调整data[i]
    private void adjust(int i, int n, int[] data) {
        if(data[i] <= data[0]) {
            return;
        }
        // 置换堆顶
        int temp = data[i];
        data[i] = data[0];
        data[0] = temp;
        // 调整堆顶
        int t = 0;
        while( (left(t) < n && data[t] > data[left(t)])
            || (right(t) < n && data[t] > data[right(t)]) ) {
            if(right(t) < n && data[right(t)] < data[left(t)]) {
                // 右孩子更小，置换右孩子
                temp = data[t];
                data[t] = data[right(t)];
                data[right(t)] = temp;
                t = right(t);
            } else {
                // 否则置换左孩子
                temp = data[t];
                data[t] = data[left(t)];
                data[left(t)] = temp;
                t = left(t);
            }
        }
    }

    // 寻找topN，该方法改变data，将topN排到最前面
    public void findTopN(int n, int[] data) {
        // 先构建n个数的小顶堆
        buildHeap(n, data);
        // n往后的数进行调整
        for(int i = n; i < data.length; i++) {
            adjust(i, n, data);
        }
    }

    // 打印数组
    public void print(int[] data) {
        for(int i = 0; i < data.length; i++) {
            System.out.print(data[i] + " ");
        }
        System.out.println();
    }

}

(友情提示：可左右滑动)

Main.java

import java.util.Random;

/**
 * @author xiaoshi on 2018/10/14.
 */
public class Main {

    public static void main(String[] args) {

        TopN topN = new TopN();

        // 第一组测试
        int[] arr1 = new int[]{56, 30, 71, 18, 29, 93, 44, 75, 20, 65, 68, 34};

        System.out.println("原数组：");
        topN.print(arr1);
        topN.findTopN(5, arr1);
        System.out.println("调整后数组：");
        topN.print(arr1);

        // 第二组测试
        int[] arr2 = new int[1000];
        for(int i=0; i<arr2.length; i++) {
            arr2[i] = i + 1;
        }

        System.out.println("原数组：");
        topN.print(arr2);
        topN.findTopN(50, arr2);
        System.out.println("调整后数组：");
        topN.print(arr2);

        // 第三组测试
        Random random =new Random();
        int[] arr3 = new int[1000];
        for(int i=0; i<arr3.length; i++) {
            arr3[i] = random.nextInt();
        }

        System.out.println("原数组：");
        topN.print(arr3);
        topN.findTopN(50, arr3);
        System.out.println("调整后数组：");
        topN.print(arr3);
    }

}

(友情提示：可左右滑动)

运行结果：

原数组：
56 30 71 18 29 93 44 75 20 65 68 34 
调整后数组：
65 68 71 75 93 18 29 30 20 44 56 34 
原数组：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100  
调整后数组：
951 952 955 954 953 956 957 963 968 964 972 961 979 959 958 967 966 969 974 965 970 973 988 962 983 993 986 981 987 992 960 976 1000 982 978 977 975 985 984 990 971 997 996 991 989 999 998 980 994 995 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 
原数组：
835636999 -90522479 -769818338 -1416245398 1041573706 1812203535 896607110 1789246766 1774883884 26722194 -418633859 1344767118 1570967674 1316806558 -1435502178 1473470755 -918439629 1869702742 2101404773 -1296472335 649689400 1153902366 -1052670714 498645159 -1530905537 -1159220094 -154125959 -868393434 -504505075 -1106082731 -494609447 -1406763201 -750828828 -342445539 -744595730 -1920006464 -1230413255 -1426324562 -1277878264 474935729 -2029054806 447026196 -1121975794 -1448358181 1957166126 1336854710 …… 
调整后数组：
1960093727 1964906931 1970688292 1975808864 1981745799 1991241336 2022661667 1981095418 1998580270 1988169309 2008783098 2027208746 2136972032 2062185334 2058314391 2003774732 2022245178 2022674254 2076406457 2024695646 2106449320 2016192325 2039153729 2043057170 2042482994 2138695524 2139809413 2121618159 2067898415 2122335504 2101895240 2100462015 2054036800 2037921932 2067998974 2117710597 2133594097 2101404773 2077564852 2033907579 2035097590 2108250457 2122256662 2138496647 2088084171 2107415856 2077919162 …… 

(友情提示：可左右滑动)

（注：由于1000个数字符过多，超了微信文章限制，结果进行了省略，大家可以本地运行查看结果）

面试官看了一下。

小史熟练地介绍起了自己的项目，由于准备充分，小史聊起来游刃有余。面试官问的几个问题也进行了详细的解释。

小史走后，面试官在系统中写下了面试评语：

【遇见吕老师】

小史回到学校哼着歌走在校园的路上，正好碰到吕老师。

小史把面试情况和吕老师说了一下。

小史：感悟还挺深的。虽然平时做过topN的问题，知道分治法时间更少。但是碰到具体问题的时候还是要具体分析，这种大数据量的情况下反而用堆会更快。

---

面试现场是互联网侦察推出的一个新的板块，旨在回放真实的面试过程，并对面试题进行全面解析，提供多种思路，比较优劣，希望对大家的面试有所帮助。

往期回顾