阅读 3423

如何在 10 亿数中找出前 1000 大的数

作者 | channingbreeze
来源公众号 | 互联网侦察
声明:已获作者授权转载

小史是一个应届生,虽然学的是电子专业,但是自己业余时间看了很多互联网与编程方面的书,一心想进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 时的一些细节。突然有了一个想法。











小史在纸上画了画。





























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

/**
 * @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();
    }

}
复制代码


面试官看了一下。





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






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





【遇见吕老师】


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







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






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






本文作者是我的好朋友欣哥,原文链接如下:

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


关注下面的标签,发现更多相似文章
评论