四种方法教你求解数组中的第 K 大元素 | 文末有福利

公众号好久没更新了，感谢各位读者的支持，没有取关。

这不，手头的事情忙的差不多的时候，就赶紧来更新文章了，而且给大家准备了福利，想知道福利是啥，先往下看吧。

确实这段事情有些事情在忙。但是回过头来看，中间还是有时间可以写点东西的。

人都是有惰性的，对于反人性的东西，人们都是不愿意主动去做的，需要有强大的自制力。而且只要中间有所松懈，就会功亏一篑。

所以我一直都认为很多时候，只要坚持下去了，那就超越了很多人。

最近又是一年一度的秋招季，我们都知道，数据结构与算法的面试是求职过程中必不可少的一个环节。

学习本来就是反人性的，再加上数据结构与算法，大家都知道，本来就不容易，还考验逻辑，自然而然就成了很多人求职路上的绊脚石了。

所以呢，我最近打算分享一些不是特别难，但是灵活性很强，面试容易问到的题目，一方面是为自己的求职做准备，另一方面呢，也是希望可以帮助到有需要的人，希望大家可以多多转发。

说实话，这些题目，并不是很难，甚至你用暴力的算法都能做出来。

但是呢，你最直接想到的方法，往往不是面试官想要考察的地方。因为你想到的，别人也能第一时间想到。

话不多说，今天我们来讲一道这样的题目：如何求无序数组中的第 K 大元素

举个例子：比如给定的无序数组如下：

array = [7, 5, 15, 3, 17, 2, 20, 24, 1, 9, 12, 8], K = 6

那么结果就是 9

怎么样，这个题不知道你碰到过没有，如果没有的话，可以先自己思考下

我首先说下哈，这个题能考察的知识点还是挺多的

第一种方法: 直接排序法

咱们首先说下第一种方法，也是最容易想到的方法，那就是给数组排序。

既然数组是无序的，那我就先将数组降序排序排列，然后输出数组下标为 K - 1 个元素就行了，因为数组下标是从 0 开始的。

对数组排序的话，直接调用库函数就行了，就算是需要自己手写，我相信大家应该也都是能写出来的。

我也用代码实现了下，放在下面了。

# -*- coding: utf-8 -*-
from typing import List


def find_K_max_number_method1(array: List[int], K: int) -> int:
    # 首先对数组进行降序排序
    sorted_array = sorted(array, reverse=True)
    # 注意下标是从 0 开始的，因此下标 K - 1 是第 K 大元素
    return sorted_array[K - 1]


if __name__ == '__main__':
    array = [7, 5, 15, 3, 17, 2, 20, 24, 1, 9, 12, 8]
    K = 6
    print(find_K_max_number_method1(array, K))

这样做的话，时间复杂度主要在排序，库函数实现的排序函数的时间复杂度都是效率非常高的，优化做的非常好，因此时间复杂度是

,空间复杂度的话，是

.

第二种方法：选择法

第二种方法是选择法，看到这个名字啊，不知道你有没有想起一种排序算法，选择排序算法。

刚才第一种方法也是基于排序的，不过呢，它考虑的是一种全局的思想，排完序以后，求解任意 K 打的元素都可以。

但是我们可以想下下面的情况，如果我们要求解的是数组的第一大元素，也就是数组的最大值，那我们也对数组进行排序，是不是有点浪费呢？

这时候，其实我们就可以按需进行了。

我们知道啊，选择排序算法的思想就是选择剩余元素的最小值（或者最大值），和当前元素进行交换。

基于这个思想，我们可以第一次选择数组的最大值，第二次选择数组第二大值，这样的操作，重复 K 次，得到的不就是数组元素的第 K 大元素吗？

我用代码实现了下，你可以看下，同时用自己熟悉的语言实现下。

def find_K_max_number_mathod2(array: List[int], K: int) -> int:
    # 进行 K 轮，每次选择剩余元素的最大值
    for i in range(K):
        index = i
        # 求解剩余元素最大值对应的下标
        for j in range(index + 1, len(array)):
            if array[j] > array[index]:
                index = j
        # 剩余元素最大值和当前值进行交换
        array[i], array[index] = array[index], array[i]
    # 返回下标为 K - 1 的元素
    return array[K - 1]

这种方法相较于第一种方法，没有完全对数组进行排序，时间复杂度是

,

是数组的长度，空间复杂度是

，表面上看，这种方法比第一种方法好，但是由于 K 是一个不确定的值，如果比较小的话，这种方法是比较好的。

但是如果 K 约等于 N 的话，那么这种方法的时间复杂度就是

了，这个时候这种方法就还不如第一种方法呢。

所以这种方法的最好时间复杂度是

,最坏时间复杂度是

。

第三种方法：堆

接下来就进入到了第三种方法了，第三种方法是基于堆进行实现的。我们这里说的堆都是二叉堆，也就是只有左孩子结点和右孩子结点。

对堆不了解的小伙伴可以把堆理解成是一种特殊的二叉树，也就是完全二叉树，而且父子结点上的元素有大小关系限制。

父节点大于等于孩子节点的，称为大顶堆，父节点小于等于孩子节点的，称为小顶堆。

堆有很多应用，比较常见的有堆排序，优先队列，维护最值等等……

今天我们用到的功能就是维护最值，这里的最值不是简单的最大值或者最小值，而且前 K 大的值。

怎么理解呢？我们可以用一个长度为 K 的小顶堆来维护数组的前 K 个元素，然后让剩下的元素和堆顶元素（堆顶存储的是最小值）进行比较，如果当前元素大于堆顶元素，则进行交换。

这样，对数组进行遍历后，整个堆维护的就是数组的前 K 大元素，而且由于这是一个小顶堆，因此堆顶元素就是第 K 大元素。

实现的代码如下，你可以看下:

def find_K_max_number_method3(array: List[int], K: int) -> int:
    # 导入相关的 package
    import heapq
    # 首先获取数组的前 K 的元素，作为堆的初始值
    heap = array[:K]
    # 将数组在线性时间内调整为堆，注意 Python 里面默认的就是小顶堆
    heapq.heapify(heap)
    for i in range(K, len(array)):
        # 如果当前元素比堆顶元素大，就对堆进行调整
        if array[i] > heap[0]:
            heapq.heapreplace(heap, array[i])
    return heap[0]

这时候的时间复杂度你还知道吗？我们一起来看下。

1. 首先对先 K 个元素进行建堆，时间复杂度是

1. 然后对剩下的 N - K 个元素进行比较调整，最坏情况下，需要对剩下的所有元素都进行调整，这是时间复杂度就是

所以整体的时间复杂度就是

,空间复杂度是

.

堆在这方面的应用还有求中位数，也是很经典的一道面试题，感兴趣的小伙伴可以自己查下。

如果你觉得这道题到这就结束了，那你说明还是年轻了。

第四种方法：快速排序的方法

其实这道题还有第四种方法，那就是基于快速排序的方法。

可能现在你觉得这两者还没有任何关系，别着急，让我为你慢慢道来。

快排是基于分治的思想，简单说就是要想整个数组元素都有序，那么我可以找到一个主元，然后让左边的元素都比主元小，右边的元素都比主元大，这样只要左右区间都有序后，整个数组就有序了，那么左右区间如何有序呢，只要再选主元，让左右区间有序就可以了，直到细分后的左右区间长度为 0， 那么就不用再左右分了，也就结束了。

那么我们如何使用快排来解决这个问题呢？

我们来看快排哈，虽然我刚才上面讲了很多，但是总结来看就是两步，第一步，选主元；第二步，对左右进行递归排序。

选择主元结束后，主元所在的有序数组的位置就确定了，因为左边元素都比它小，右边的元素都比它大。所以它就是数组的第 index 大元素，index 这里代表数组主元所对应的下标。如果 index == K - 1，那么这不就是我们要找的第 K 大元素，如果index < K - 1,那么说明第 K 大元素在右区间，否则在左区间。

代码实现是这样的，可能有点难理解，需要你多读几遍。

def find_K_max_number_method4(array: List[int], K: int) -> int:
    # 首先确定边界
    left, right = 0, len(array) - 1
    # 选定主元
    partition = array[left]
    while left < right:
        # 这里我们进行降序分区，也就是左区间值 > 主元，主元 > 右区间的值
        while left < right and array[right] <= partition:
            right -= 1
        array[left] = array[right]
        while left < right and array[left] > partition:
            left += 1
        array[right] = array[left]
    array[right] = partition
    # 如果 right == K - 1，目标已经找到了
    if right == K - 1:
        return array[right]
    # 如果 right < K - 1，那么在右区间查找第 K - 1 - right 大元素
    elif right < K - 1:
        return find_K_max_number_method4(array[right + 1:], K - 1 - right)
    # 否则在左区间查找第 K 大元素
    else:
        return find_K_max_number_method4(array[:right], K)

这种方法的时间复杂度是

,

是数组的长度，空间复杂度是

. 具体是怎么得到的这里就不具体说了，感兴趣的小伙伴可以自己查下。

最后的主函数代码是这样的：

if __name__ == '__main__':
    array = [7, 5, 15, 3, 17, 2, 20, 24, 1, 9, 12, 8]
    K = 6
    print(find_K_max_number_method1(array[:], K))

    print(find_K_max_number_mathod2(array[:], K))

    print(find_K_max_number_method3(array[:], K))

    print(find_K_max_number_method4(array[:], K))

好了，这道题到这里就算圆满结束了。

它考察的知识点还是挺多的，前两种方法是比较常见的方法，这里就不再说了，第三种方法需要你对堆有一个比较深入的掌握了解，并且结合着这道题进行解答。

第四种方法首先需要你对快排有一个透彻的理解掌握，然后才能基于快排进行改进。

最后，不知道你有没有个疑问，那就是我现在也只是个学生，我是如何哪些题是面试的时候容易遇到呢？

确实，我现在基本上还没有怎么参加过面试，这个题目一方面我是在 LeetCode 平台有遇到过。但是呢，现在 LeetCode 平台已经有 2000 多道题了，就算有很多的时间，也很少有人能把所有题都刷一遍，而且，就算刷了一遍，也很难完全掌握。

如果有人能够把一些面试常见的题目进行总结的话，学会了这些有代表性的题目，自然而然就能举一反三了。

这时候，《漫画算法 2 小灰的算法进阶》就要出场了，我们今天的福利也是抽奖送 3 本这本书。

这本书利用漫画的形式来生动形象的讲解面试中常见的算法，对于新手来说，很是友好，在豆瓣上受到了很多网友的好评。

而且我最欣赏的一点就是这本书总结了一些面试中常考常问的算法，这是作者大厂工作经验的总结，能够帮助求职者直接抓住核心，直奔要点。

我今天讲解的这道题目，这本书中也有收录，而且还有其他的一些常见的算法题目，比如说我之前讲过的三数之和，类似的还有很多。

对于书中讲解本题最后一种方法的内容，我截了一张图，小伙伴们可以看下，很 nice。

希望大家可以积极参与，参与方式，公众号后台回复「漫画算法」，即可参与抽奖，本周五（7 月2 日）晚 20:00 开奖。另外有问题的话，也可以添加我的微信:yuniXiaomn，进行交流。

如果没有中奖，有需要的小伙伴也可以点击阅读原文进行购买，当下还有满 100 减 50 的优惠活动。