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

秒速五厘米 2021-12-19 01:51 231阅读 0赞

点击蓝色“五分钟学算法”关注我哟

加个“星标”，一起学算法

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg]

作者 | channingbreeze

来源 | 互联网侦察

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 1]

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

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 2]

**【面试现场】**

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 3]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 4]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 5]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 6]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 7]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 8]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 9]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 10]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 11]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 12]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 13]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 14]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 15]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 16]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 17]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 18]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 19]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 20]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 21]

半分钟过去了。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 22]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 23]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 24]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 25]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 26]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 27]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 28]

小史一时慌了神。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 29]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 30]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 31]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 32]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 33]

小史在纸上画了画。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 34]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 35]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 36]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 37]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 38]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 39]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 40]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 41]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 42]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 43]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 44]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 45]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 46]

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

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

面试官看了一下。

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 47]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 48]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 49]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 50]

**【遇见吕老师】**

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 51]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 52]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 53]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 54]

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

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 55]

![640?wx\_fmt=jpeg][640_wx_fmt_jpeg 56]

--------------------

## END ##

## ![640?wx\_fmt=png][640_wx_fmt_png] ##

**原 创 热 文 推 荐**

☞[毕业十年后，我忍不住出了一份程序员的高考试卷][Link 1]

[☞][Link 2][一道腾讯面试题：厉害了我的杯][Link 3]

[☞][Link 4][十大经典排序算法动画与解析，看我就够了][Link 5]

[☞][Link 4][这或许是东半球分析十大排序算法最好的一篇文章][Link 6]

[☞][Link 4][面试官，我会写二分查找法！对，没有 bug 的那种！][bug]

![640?wx\_fmt=png][640_wx_fmt_png 1] 你点的每个“在看”，我都认真当成了喜欢

[640_wx_fmt_jpeg]: /images/20211219/7e57589072b74e7e98a3eba2b4a54966.png
[640_wx_fmt_jpeg 1]: /images/20211219/0ac70451f7664f09a6bc3820bb9bd43a.png
[640_wx_fmt_jpeg 2]: /images/20211219/c44d6de08ab846c2810c5bc5405d3779.png
[640_wx_fmt_jpeg 3]: /images/20211219/f8c8ec53723d4ad4b2cc5b18ccb06c19.png
[640_wx_fmt_jpeg 4]: /images/20211219/13c849de29874356959c58141324c126.png
[640_wx_fmt_jpeg 5]: /images/20211219/e4034df042884ccd9e1cc01a1a703928.png
[640_wx_fmt_jpeg 6]: /images/20211219/f34dfa96607548a9bfe5275cc83787d1.png
[640_wx_fmt_jpeg 7]: /images/20211219/74950cbd8eb8479eaa39a50168f048c6.png
[640_wx_fmt_jpeg 8]: /images/20211219/70bfd2ac911e4ffca09be121860ead1c.png
[640_wx_fmt_jpeg 9]: /images/20211219/52704e798468456290fd7bbc2b07b6d6.png
[640_wx_fmt_jpeg 10]: /images/20211219/ae0b6753d3df49ec98423709277c6243.png
[640_wx_fmt_jpeg 11]: /images/20211219/aa7c215c2c544ae7ba80725b3aa5c6e7.png
[640_wx_fmt_jpeg 12]: /images/20211219/f35cc085bf8c410d9bda0694a5dd4b4c.png
[640_wx_fmt_jpeg 13]: /images/20211219/b883d31f22594ba691fa0aab833592d9.png
[640_wx_fmt_jpeg 14]: /images/20211219/a3c080f00b5a4976b7628e8ff3d2c562.png
[640_wx_fmt_jpeg 15]: /images/20211219/1cb28c800630432eb1f681c2ec428b78.png
[640_wx_fmt_jpeg 16]: /images/20211219/f6ec16c935b549749a0e32391d278ec7.png
[640_wx_fmt_jpeg 17]: /images/20211219/c703583ca8c7464193c0af99caddf2b8.png
[640_wx_fmt_jpeg 18]: /images/20211219/984fcfb17448440c8f2503bfb94151ed.png
[640_wx_fmt_jpeg 19]: /images/20211219/f54bed2794024a3c91fcf7bf38bf2008.png
[640_wx_fmt_jpeg 20]: /images/20211219/4e05d68a2272467a84137b0398bcce1b.png
[640_wx_fmt_jpeg 21]: /images/20211219/e4da79c3d0914c589c29b31e6ed00278.png
[640_wx_fmt_jpeg 22]: /images/20211219/bc406997ed6e4022aa26db067417ce3a.png
[640_wx_fmt_jpeg 23]: /images/20211219/2a29c80e46f74bb6876a67e84df244af.png
[640_wx_fmt_jpeg 24]: /images/20211219/f3b416a362284181806eae9b95a5ec61.png
[640_wx_fmt_jpeg 25]: /images/20211219/97a57df74009439c862754008a160104.png
[640_wx_fmt_jpeg 26]: /images/20211219/42eb5add6fc3461696047623af796601.png
[640_wx_fmt_jpeg 27]: /images/20211219/ba6e77f1926045f48927f91578854c72.png
[640_wx_fmt_jpeg 28]: /images/20211219/769f80359c6640a9903008a7be4938cf.png
[640_wx_fmt_jpeg 29]: /images/20211219/f9aabff302b942fc8e97996e92fd94fe.png
[bitmap]: http://mp.weixin.qq.com/s?__biz=MzIzMTE1ODkyNQ==&mid=2649409856&idx=1&sn=448772acaf9b2f1a87f4d7c1caf4caa9&chksm=f0b60ca2c7c185b4cb93d0deffed461e6ba3e421e362c17102415e351a496792fa26e0282dc0&scene=21#wechat_redirect
[640_wx_fmt_jpeg 30]: /images/20211219/c96e03886b6447d28297d26c808130b4.png
[640_wx_fmt_jpeg 31]: /images/20211219/f3525629c3194610b5f36b308d7f14ff.png
[640_wx_fmt_jpeg 32]: /images/20211219/fcec104f687e429583099bd344e8453e.png
[640_wx_fmt_jpeg 33]: /images/20211219/48f6c5ada14e4f09ba8f97282b08233d.png
[640_wx_fmt_jpeg 34]: /images/20211219/b75fbe12059348f1ae9460a262e9ee44.png
[640_wx_fmt_jpeg 35]: /images/20211219/92c30df1abd145198cd3c332d980a66c.png
[640_wx_fmt_jpeg 36]: /images/20211219/518bdbef78504d008ca774c65ba3e32a.png
[640_wx_fmt_jpeg 37]: /images/20211219/9070df5e76064ad9bffd5b767289ad9c.png
[640_wx_fmt_jpeg 38]: /images/20211219/14b85eda54bf4f3ca557e133443be8ce.png
[640_wx_fmt_jpeg 39]: /images/20211219/edcda44ef6fa49a1aff7b5ba5700ae90.png
[640_wx_fmt_jpeg 40]: /images/20211219/becfe7cb881c4821b2c5211b76298cae.png
[640_wx_fmt_jpeg 41]: /images/20211219/17c3e69aa4054129955d3dec0fb98da0.png
[640_wx_fmt_jpeg 42]: /images/20211219/03dd68f7955e4b9ea5d6f34fa4b86723.png
[640_wx_fmt_jpeg 43]: /images/20211219/8430371657704c589f0cadc7d50844b5.png
[640_wx_fmt_jpeg 44]: /images/20211219/dadb3d477bb9436485e8fac551743435.png
[640_wx_fmt_jpeg 45]: /images/20211219/e01fe9e1416b41e39b4e2b3124ad2b34.png
[640_wx_fmt_jpeg 46]: /images/20211219/f6986323a28647e4a90a4e76f0446d96.png
[640_wx_fmt_jpeg 47]: /images/20211219/6f11acc3fe5644b8b349afa500dc8eef.png
[640_wx_fmt_jpeg 48]: /images/20211219/85eab52b0d314095959141f0e9443ec8.png
[640_wx_fmt_jpeg 49]: /images/20211219/885652c291a94c0590dcbcac82ebd80f.png
[640_wx_fmt_jpeg 50]: /images/20211219/9cc3d65073d347678a9c02acef90eb6f.png
[640_wx_fmt_jpeg 51]: /images/20211219/231c3b504efb41199c6e099892604fe3.png
[640_wx_fmt_jpeg 52]: /images/20211219/7e6b538f01ca4987a63375b2666c0b7b.png
[640_wx_fmt_jpeg 53]: /images/20211219/d50d64add3264d14b94fda457635ad77.png
[640_wx_fmt_jpeg 54]: /images/20211219/81cfe75e966243feba2da60401f041ea.png
[640_wx_fmt_jpeg 55]: /images/20211219/0cd808a0c8af4f219474c5f6acd2b3ff.png
[640_wx_fmt_jpeg 56]: /images/20211219/ec42e74193fe4c83a8a9646f654fb907.png
[640_wx_fmt_png]: /images/20211219/7456093ab89146aa9d93e4b397904352.png
[Link 1]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/91488249
[Link 2]: http://mp.weixin.qq.com/s?__biz=MzA5MzY4NTQwMA==&mid=2651011536&idx=3&sn=fd5ff61a84fe2180a7c21d15acf71659&chksm=8bad8a27bcda03319570ae23d05392d287390a51ca94014422dd199450b25f43467aaaedb59e&scene=21#wechat_redirect
[Link 3]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247484557&idx=1&sn=739d80488fe1169a9c9ca26ecfcdfba6&chksm=fa0e6b0ccd79e21a1c2b0d99db69f6206cddddfe2367742e9de1d7d17ec35a5ce29fa4e30d63&scene=21#wechat_redirect
[Link 4]: http://mp.weixin.qq.com/s?__biz=MzA5MjcxNjc2Ng==&mid=2650560116&idx=1&sn=f9e86fa3e7b15624177b29ef1a785be4&chksm=88601dc5bf1794d30fd595d413491da189584b44fd2b2e5e40c665e58760e162616585811647&scene=21#wechat_redirect
[Link 5]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/87910210
[Link 6]: https://blog.csdn.net/dQCFKyQDXYm3F8rB0/article/details/92825279
[bug]: http://mp.weixin.qq.com/s?__biz=MzUyNjQxNjYyMg==&mid=2247485240&idx=1&sn=fbccc747b2e8558c6478171709005ff9&chksm=fa0e68b9cd79e1af5ab68d42adea0b24c7d4867069091df9e95b6f20ab57b69c4e38994a36be&scene=21#wechat_redirect
[640_wx_fmt_png 1]: /images/20211219/df11182f1a674c28bab5833300e7f030.png