面试官：找出数组中的第 6 大元素，我直接懵逼了。。

阳光穿透心脏的1/2处 2022-10-06 12:57 148阅读 0赞

**点击关注公众号，Java干货****及时送达**![889852d4c1bd0bed54a4fcc62eb7c7aa.png][]

![217ed37cde9f965db64eca62f350bfa7.png][]

![4f996f43be33d548479f5c6386c8ddd8.png][]

第二天，在另一家公司……

小灰是吧？请简单介绍一下你自己。![3689d64cc2a241b56f9935d6bef5a7db.png][]![522a6add96040f70db92cca8b2288646.png][]

![73bca4613cef891415fefed7f8191112.png][] ![9408e9059a9847d6ae66a982fd2091c6.png][]好的，blah blah blah……

下面考你一道算法题：

给你一个无序数组，要求你找出数组中的第k大元素。![7d29d6b4d46e7e8bd3b2c5f4c92aaaa6.png][]![bab23456159c433748f82830a0c2cd67.png][]

题目是什么意思呢？比如给定的无序数组如下：

![60d94a4be11102ada3a3fc13091f2dff.png][]

如果 k=6，也就是要寻找数组中的第6大元素，这个元素是哪一个呢？

显然，数组中第一大的元素是24，第二大的元素是20，第三大的元素是17 ......**第6大的元素是9**。

![d9a3432fc9c7e90d0246097c997f3047.png][]

![61ff9196104c01c301743508f3c57fa5.png][]![2ed8ea8776f8a395f9e193cdd26a91d0.png][]让我想想啊……

![e43b7f928709d744324186dd36990335.png][]对了，我可以先把无序数组排序，然后数出排序后的第k个元素！

**方法1：排序法**

这是最容易想到的方法，先把无序数组从大到小进行排序，排序后的第k个元素，自然就是数组中的第k大元素。

![937f053a205a9425666f9c0c4c419f03.png][]

先进行排序的话，算法时间复杂度是O（nlogn），

性能有些差，有没有更优化的方法？![3e38a61e9e185773b4ba0c6bbe11dd91.png][]![f83446397ca11038626f7f0ffbaea782.png][]

![c3756fd8f633a8ef58bc5f701b045737.png][]让我想想啊……

![b5c1d23ef5268079b72de83b895db451.png][]对了，我可以维护一个长度为k的数组，有序存储当前k个较大的元素！

**方法2：插入法**

维护一个长度为k的有序数组A，用于存储已知的k个较大的元素。

接下来遍历原数组，每遍历到一个元素，和数组A中最小的元素相比较，如果小于等于数组A的最小元素，继续遍历；如果大于数组A的最小元素，则插入到数组A中，并把曾经的最小元素“挤出去”。

比如k=3，先把最左侧的7,5,15三个数有序放入数组A当中，代表当前最大的3个数。

![5054c0694a82b1feda45247c42236519.png][]

这时候，遍历到元素3， 由于3<5，继续遍历。

![d595bec0c15a343cdd23904d8130d114.png][]

接下来遍历到17，由于17>5，插入到数组A的合适位置，类似于插入排序，并把原先最小的元素5“挤出去”。

![18263d6450bc304415578524d5e7ce46.png][]

继续遍历原数组，一直遍历到数组的最后一个元素......

最终，数组A中存储的元素是24,20,17，代表着整个数组中最大的3个元素。此时数组A中最小的元素17，就是我们要寻找的第k大元素。

![c8e0f74c7c05b80a6b6024da443535c4.png][]

这个方法的时间复杂度是O（nk），如果k的值比较大，其性能可能还不如方法一。

![663042b97a90f9c411b4057ba1894c5f.png][]![61d6b5865aed2cf8e7cc7cc1c12e9546.png][]还有没有更优化的方案？![145a9dae408fe73a6cd2917271a5d60b.png][]

![51885ce2a0dc6913060cbc2ce9c7c102.png][]好像没有更快的方法了吧……

呵呵，没关系，回家等通知去吧！![c213fcded524a948b7672a4d7b2b40b7.png][]![541a9857d631d6f30ddb60433fb9b258.png][]

**解题思路**

小灰，你刚刚去面试了？结果怎么样？![edc8447f4377a5e0f48189877671e37f.png][]![3ec7d0b91f556f27ee33541076447ead.png][]

![ffffa4cdafa74366935c7502714386ae.png][]![d8fea2aa112b8a17c3bb97e6bdea396b.png][]唉……

![37c52413cbdebd330a8f07ea83a31aa6.png][]![f43071fd78cb86581dfc9a9199ee3476.png][]大黄，要想找到无序数组中的第k大元素，有什么性能较高的方法吗？

这是一道很经典的算法题，解法有很多种，

其中最容易想到的是利用二叉堆来解决。![7f320945d8ac243b734d72aa7084943a.png][]

关于二叉堆的概念，在上一本《漫画算法》中我们介绍过。简而言之，二叉堆是一种特殊的完全二叉树，它包含最大堆和最小堆两种形式。

其中最小堆的特点，是每一个父结点都小于等于自己的子结点，堆顶是整个堆中最小的结点。要解决这个算法题，我们可以利用最小堆的特性。

![1732e3f6674cd6763b5020254c505ebc.png][]可是，最小堆和这个算法题究竟有什么关系呢？

别急，让我来解释一下这个方法的思路。![840313cfde306d78bf64ca655b93da75.png][]![2b2421b33264a601cb5ce095397f4e75.png][]

**方法3：最小堆法**

维护一个容量为k的最小堆，堆中的k个结点代表着数组当前**最大的k个元素**，而堆顶显然是这k个元素中的**最小值**。

遍历原数组，每遍历一个元素，就和堆顶比较，如果当前元素小于等于堆顶，说明该元素一定不是最大的k个元素之一，继续遍历；如果元素大于堆顶，说明该元素有可能是最大的k个元素之一，把当前元素放在堆顶位置，并调整二叉堆（下沉操作）。

遍历结束后，堆顶就是数组的**最大k个元素中的最小值**，也就是**第k大元素**。

假设k=5，具体的执行步骤如下：

**1. 把数组的前k个元素构建成堆。**

![c972b193d0ec1ff8cdc89c9120da5b5f.png][]

![75d427612f7d44bec875a48ca63f257e.png][]

**2. 继续遍历数组，和堆顶比较，如果小于等于堆顶，则继续遍历；如果大于堆顶，则取代堆顶元素并调整堆。**

遍历到元素2，由于 2<3，所以继续遍历。

![bb12138ded30330294d96822b3cd2dac.png][]![e764aa413658319dc6840b234dc087bb.png][]

遍历到元素20，由于 20>3，20取代堆顶位置，并调整堆。

![4106ff5c832d8aa9a859e0543131843b.png][]

![b24140629ada8ff64ade2d05ccf778dd.png][]

![7fde02dad1588416f6da3e4f94e76a03.png][]![ab23565e307972d237b98b52cd93a485.png][]

遍历到元素24，由于 24>5，24取代堆顶位置，并调整堆。

![e79a7337355a1bc9017d6ce3b51e1849.png][]

![0c17831587e260db6c9ed89589f20714.png][]

以此类推，我们一个一个遍历元素，当遍历到最后一个元素8的时候，最小堆的情况如下：

![b65a75635a0c8508b87226db9cddcc78.png][]![6358449515dd8698d2e644883cfa19ff.png][]

**3. 此时的堆顶，就是堆中的最小值，也就是数组中的第k大元素。**

![14f5c35898ad24516534a6cdd4921379.png][]![0656daa878caf08dd21eacf96662da80.png][]

这个方法的时间复杂度是多少呢？

*  构建堆的时间复杂度是 O（k）
 *  遍历剩余数组的时间复杂度是O（n-k）
 *  每次调整堆的时间复杂度是 O（logk）

其中2和3是嵌套关系，1和2,3是并列关系，所以总的最坏时间复杂度是**O（（n-k）logk + k）**。当k远小于n的情况下，也可以近似地认为是**O（nlogk）**。

这个方法的空间复杂度是多少呢？

刚才我们在详细步骤中把二叉堆单独拿出来演示，是为了便于理解。但如果允许改变原数组的话，我们可以把数组的前k个元素“原地交换”来构建成二叉堆，这样就免去了开辟额外的存储空间。

因此，这个方法的空间复杂度是O（1）。

![7baa79b474f2bc7da67ad92aab18c6f1.png][]明白了，最小堆法还真是个巧妙的解决方法！怎么用代码来实现呢？

代码很简单，让我们来看一看：![1fa035c460017aa4530b4fe0db21d837.png][]![802bb8fe510215f2bd6fd75ce7cf60a9.png][]

public class KthLargestNumber {
        /**
         * 寻找第k大的元素
         * @param array  待调整的堆
         * @param k  第几大
         */
        public static int findKthLargestNumber(int[] array, int k) {
            //1.用前k个元素构建最小堆
            buildHeap(array, k);
            //2.继续遍历数组，和堆顶比较
            for (int i = k; i < array.length; i++) {
                if (array[i] > array[0]) {
                    array[0] = array[i];
    
    
                    downAdjust(array, 0, k);
                }
            }
            //3.返回堆顶元素
            return array[0];
        }
    
    
        /**
         * 构建堆
         * @param array  待调整的堆
         * @param length  堆的有效大小
         */
        private static void buildHeap(int[] array, int length) {
            // 从最后一个非叶子结点开始，依次下沉调整
            for (int i = (length - 2) / 2; i >= 0; i--) {
                downAdjust(array, i, length);
            }
        }
    
    
        /**
         * 下沉调整
         * @param array     待调整的堆
         * @param index    要下沉的结点
         * @param length    堆的有效大小
         */
        private static void downAdjust(int[] array, int index, int length) {
            // temp保存父结点值，用于最后的赋值
            int temp = array[index];
            int childIndex = (2 * index) + 1;
    
    
            while (childIndex < length) {
                // 如果有右孩子，且右孩子小于左孩子的值，则定位到右孩子
                if (((childIndex + 1) < length) &&
                        (array[childIndex + 1] < array[childIndex])) {
                    childIndex++;
                }
                // 如果父结点小于任何一个孩子的值，直接跳出
                if (temp <= array[childIndex]) {
    
    
                    break;
                }
                //无需真正交换，单向赋值即可
                array[index] = array[childIndex];
                index = childIndex;
                childIndex = (2 * childIndex) + 1;
            }
    
    
            array[index] = temp;
        }
    
    
        public static void main(String[] args) {
            int[] array = new int[] { 7, 5, 15, 3, 17, 2, 20, 24, 1, 9, 12, 8 };
            System.out.println(findKthLargestNumber(array, 5));
        }
    }

![8a4de29b2eca92fb1889d96a33d36797.png][]原来如此，这下彻底明白啦！

要寻找数组的第k大元素，其实还有一种方法，这种方法就是**分治法**![23196230e1e896e3552500137ce74609.png][]![9dddd463e5145e6228fe0ba24f0fa400.png][]

**方法4：分治法**

大家都了解快速排序，快速排序利用分治法，每一次把数组分成较大和较小的两部分。

我们在寻找第k大元素的时候，也可以利用这个思路，以某个元素a为基准，把大于a的元素都交换到数组左边，小于a的元素都交换到数组右边。

比如我们选择以元素7作为基准，把数组分成了左侧较大，右侧较小的两个区域，交换结果如下：

![4358e520d212fb0f34202aeecc08a5cf.png][]

包括元素7在内的较大元素有8个，但我们的k=5，显然较大元素的数目过多了。于是我们在较大元素的区域继续分治，这次以元素12位基准：

![1c6b3c04c98b66990bc3dec203d4b615.png][]

这样一来，包括元素12在内的较大元素有5个，正好和k相等。所以，基准元素12就是我们所求的。

这就是分治法的大体思想，这种方法的时间复杂度甚至优于最小堆法，可以达到O（n）。有兴趣的小伙伴可以尝试用代码实现一下。

好了，关于寻找数组第k大元素的方法，我们就介绍到这里，

想要了解更多内容，可以阅读《漫画算法2》哦！![95d2234eccf1f59897c744aeb685db11.png][]![8404661d8ce347e71d46d32d9ab61f1b.png][]

**▊《****漫画算法2：小灰的算法进阶****》**

魏梦舒（@程序员小灰） 著

*  全网阅读量近2000万的漫画算法故事
 *  和快乐的小仓鼠一起搞定数据结构和算法，从容面试

本书是《漫画算法：小灰的算法之旅》的续作，通过主人公小灰的心路历程，用漫画的形式讲述了多个数据结构、算法及复杂多变的算法面试题目。

![b93365a491abe6dd1b488ee08cf55acc.png][]

（限时五折包邮，快快扫码抢购吧！）

**免费送书福利：**

正值端午佳节之际，栈长这几天会从精选留言中选出 5 个人，每个人送出一本《漫画算法2》免费包邮送到家，欢迎留言，说不定就是你 ^\_^

最后祝各位小伙伴端午安康～

[889852d4c1bd0bed54a4fcc62eb7c7aa.png]: /images/20221005/2d61712996f747129da52f90a37344d4.png
[217ed37cde9f965db64eca62f350bfa7.png]: /images/20221005/c1ae4004e18e4e4babc9e989ee5d6bf2.png
[4f996f43be33d548479f5c6386c8ddd8.png]: /images/20221005/7f3729709ec24df585c49fae13ba562c.png
[3689d64cc2a241b56f9935d6bef5a7db.png]: https://img-blog.csdnimg.cn/img_convert/3689d64cc2a241b56f9935d6bef5a7db.png
[522a6add96040f70db92cca8b2288646.png]: /images/20221005/48f940f666c64faaa4a7796ba34f98c8.png
[73bca4613cef891415fefed7f8191112.png]: https://img-blog.csdnimg.cn/img_convert/73bca4613cef891415fefed7f8191112.png
[9408e9059a9847d6ae66a982fd2091c6.png]: /images/20221005/28add773ef82487194a8860087690a27.png
[7d29d6b4d46e7e8bd3b2c5f4c92aaaa6.png]: https://img-blog.csdnimg.cn/img_convert/7d29d6b4d46e7e8bd3b2c5f4c92aaaa6.png
[bab23456159c433748f82830a0c2cd67.png]: /images/20221005/cc4e9782316f479c9a1e7e593d64cb77.png
[60d94a4be11102ada3a3fc13091f2dff.png]: /images/20221005/5b26d99d60e64ea592b501584a6c0cf5.png
[d9a3432fc9c7e90d0246097c997f3047.png]: /images/20221005/c7e173dfaf4f4e089059349227cabbbd.png
[61ff9196104c01c301743508f3c57fa5.png]: https://img-blog.csdnimg.cn/img_convert/61ff9196104c01c301743508f3c57fa5.png
[2ed8ea8776f8a395f9e193cdd26a91d0.png]: /images/20221005/c6e75239d1cd44be8eeb40271355cd35.png
[e43b7f928709d744324186dd36990335.png]: /images/20221005/b362f36bc0a6448ba0a474fef1228085.png
[937f053a205a9425666f9c0c4c419f03.png]: /images/20221005/ddb0cf66ac7744f085cad8928a4dca95.png
[3e38a61e9e185773b4ba0c6bbe11dd91.png]: https://img-blog.csdnimg.cn/img_convert/3e38a61e9e185773b4ba0c6bbe11dd91.png
[f83446397ca11038626f7f0ffbaea782.png]: /images/20221005/24fbf08a4fc44e68a724060afe735658.png
[c3756fd8f633a8ef58bc5f701b045737.png]: /images/20221005/7b19f891a0ee4a4baae90dc244d4e779.png
[b5c1d23ef5268079b72de83b895db451.png]: /images/20221005/65669633ddf9429484d81dd6fae847e0.png
[5054c0694a82b1feda45247c42236519.png]: /images/20221005/21e354e39b9045b1ac8a7a35e2d2215c.png
[d595bec0c15a343cdd23904d8130d114.png]: /images/20221005/862ada971eda4c11968e2c93ab879073.png
[18263d6450bc304415578524d5e7ce46.png]: /images/20221005/c8367affab9d4053a658af669d6f2e50.png
[c8e0f74c7c05b80a6b6024da443535c4.png]: /images/20221005/345de0c94f784e3faad31f2cade57bb9.png
[663042b97a90f9c411b4057ba1894c5f.png]: https://img-blog.csdnimg.cn/img_convert/663042b97a90f9c411b4057ba1894c5f.png
[61d6b5865aed2cf8e7cc7cc1c12e9546.png]: https://img-blog.csdnimg.cn/img_convert/61d6b5865aed2cf8e7cc7cc1c12e9546.png
[145a9dae408fe73a6cd2917271a5d60b.png]: /images/20221005/091775ca732d4984b72c1fa7292d9ba6.png
[51885ce2a0dc6913060cbc2ce9c7c102.png]: /images/20221005/64216d27c8b241dbb6f20a526f1129c3.png
[c213fcded524a948b7672a4d7b2b40b7.png]: https://img-blog.csdnimg.cn/img_convert/c213fcded524a948b7672a4d7b2b40b7.png
[541a9857d631d6f30ddb60433fb9b258.png]: /images/20221005/2645c9f7c5f54df795be789f78eb4141.png
[edc8447f4377a5e0f48189877671e37f.png]: https://img-blog.csdnimg.cn/img_convert/edc8447f4377a5e0f48189877671e37f.png
[3ec7d0b91f556f27ee33541076447ead.png]: /images/20221005/f7e015ea14fb49a29331c06f9470c869.png
[ffffa4cdafa74366935c7502714386ae.png]: https://img-blog.csdnimg.cn/img_convert/ffffa4cdafa74366935c7502714386ae.png
[d8fea2aa112b8a17c3bb97e6bdea396b.png]: /images/20221005/f85453e1e9444476bb37dc1c89ea82f5.png
[37c52413cbdebd330a8f07ea83a31aa6.png]: https://img-blog.csdnimg.cn/img_convert/37c52413cbdebd330a8f07ea83a31aa6.png
[f43071fd78cb86581dfc9a9199ee3476.png]: /images/20221005/2b4693d769114e37a2f768a7bab03864.png
[7f320945d8ac243b734d72aa7084943a.png]: /images/20221005/7f4626f94b7248dcb8f79e5137a29b32.png
[1732e3f6674cd6763b5020254c505ebc.png]: /images/20221005/6824ade2ea9a4a3580240d1f5e33413f.png
[840313cfde306d78bf64ca655b93da75.png]: https://img-blog.csdnimg.cn/img_convert/840313cfde306d78bf64ca655b93da75.png
[2b2421b33264a601cb5ce095397f4e75.png]: /images/20221005/7564bde87f7a415db7a544cd771635f0.png
[c972b193d0ec1ff8cdc89c9120da5b5f.png]: /images/20221005/20a98151d48f4a51aea5aade6f4fe7d9.png
[75d427612f7d44bec875a48ca63f257e.png]: /images/20221005/35e145f087664f16b6ed0400837515b3.png
[bb12138ded30330294d96822b3cd2dac.png]: https://img-blog.csdnimg.cn/img_convert/bb12138ded30330294d96822b3cd2dac.png
[e764aa413658319dc6840b234dc087bb.png]: /images/20221005/c243ea55838743d1a18e5547818102ef.png
[4106ff5c832d8aa9a859e0543131843b.png]: /images/20221005/20f43ea8e9e84b6bba1ce1fa21796a59.png
[b24140629ada8ff64ade2d05ccf778dd.png]: /images/20221005/c393de20d776433a8deda895999b8964.png
[7fde02dad1588416f6da3e4f94e76a03.png]: https://img-blog.csdnimg.cn/img_convert/7fde02dad1588416f6da3e4f94e76a03.png
[ab23565e307972d237b98b52cd93a485.png]: /images/20221005/95cae126b84042f9bc2c6f2169a7c7fd.png
[e79a7337355a1bc9017d6ce3b51e1849.png]: /images/20221005/ef45a185eb9648c694ec7f274581306f.png
[0c17831587e260db6c9ed89589f20714.png]: /images/20221005/9e29aeebfabf43baba5b868fc3e66e5b.png
[b65a75635a0c8508b87226db9cddcc78.png]: https://img-blog.csdnimg.cn/img_convert/b65a75635a0c8508b87226db9cddcc78.png
[6358449515dd8698d2e644883cfa19ff.png]: /images/20221005/274d685479e24b23a32edf5ab70a424e.png
[14f5c35898ad24516534a6cdd4921379.png]: https://img-blog.csdnimg.cn/img_convert/14f5c35898ad24516534a6cdd4921379.png
[0656daa878caf08dd21eacf96662da80.png]: /images/20221005/22d067cd8a554c49ae7ad15ca40e1cdd.png
[7baa79b474f2bc7da67ad92aab18c6f1.png]: /images/20221005/2d5d8ba1c1554fa59ace5c1ec2c8cc26.png
[1fa035c460017aa4530b4fe0db21d837.png]: https://img-blog.csdnimg.cn/img_convert/1fa035c460017aa4530b4fe0db21d837.png
[802bb8fe510215f2bd6fd75ce7cf60a9.png]: /images/20221005/cb55f86ac56a457c9c5b46c5d1a56e53.png
[8a4de29b2eca92fb1889d96a33d36797.png]: /images/20221005/7bebd484398d485b8586e681180d0ab0.png
[23196230e1e896e3552500137ce74609.png]: https://img-blog.csdnimg.cn/img_convert/23196230e1e896e3552500137ce74609.png
[9dddd463e5145e6228fe0ba24f0fa400.png]: /images/20221005/8c1505d5ac994b5285ee5465abfd3270.png
[4358e520d212fb0f34202aeecc08a5cf.png]: /images/20221005/e8f54c4902714aeba5e7ee6345126716.png
[1c6b3c04c98b66990bc3dec203d4b615.png]: /images/20221005/ed5cd8ea4f35436c99b04a8dbb8aa22a.png
[95d2234eccf1f59897c744aeb685db11.png]: https://img-blog.csdnimg.cn/img_convert/95d2234eccf1f59897c744aeb685db11.png
[8404661d8ce347e71d46d32d9ab61f1b.png]: /images/20221005/6b95096791b148678ccb0d1f34fec396.png
[b93365a491abe6dd1b488ee08cf55acc.png]: /images/20221005/466e25735314462d9c137c51edaf9dbc.png