散文精选网公众号好久没更新了，感谢各位读者的支持，没有取关。
这不，手头的事情忙的差不多的时候，就赶紧来更新文章了，而且给大家准备了福利，想知道福利是啥，先往下看吧。
确实这段事情有些事情在忙。但是回过头来看，中间还是有时间可以写点东西的。
人都是有惰性的，对于反人性的东西，人们都是不愿意主动去做的，需要有强大的自制力。而且只要中间有所松懈，就会功亏一篑。
所以我一直都认为很多时候，只要坚持下去了，那就超越了很多人。
最近又是一年一度的秋招季，我们都知道，数据结构与算法的面试是求职过程中必不可少的一个环节。
学习本来就是反人性的，再加上数据结构与算法，大家都知道，本来就不容易，还考验逻辑，自然而然就成了很多人求职路上的绊脚石了。
所以呢，我最近打算分享一些不是特别难，但是灵活性很强，面试容易问到的题目，一方面是为自己的求职做准备，另一方面呢，也是希望可以帮助到有需要的人，希望大家可以多多转发。
说实话，这些题目，并不是很难，甚至你用暴力的算法都能做出来。
但是呢，你最直接想到的方法，往往不是面试官想要考察的地方。因为你想到的，别人也能第一时间想到。
话不多说，今天我们来讲一道这样的题目：如何求无序数组中的第K大元素
举个例子：比如给定的无序数组如下：
array=[7,5,15,3,17,2,20,24,1,9,12,8],K=6
那么结果就是9
怎么样，这个题不知道你碰到过没有，如果没有的话，可以先自己思考下
我首先说下哈，这个题能考察的知识点还是挺多的
第一种方法:直接排序法
咱们首先说下第一种方法，也是最容易想到的方法，那就是给数组排序。
既然数组是无序的，那我就先将数组降序排序排列，然后输出数组下标为K-1个元素就行了，因为数组下标是从0开始的。
对数组排序的话，直接调用库函数就行了，就算是需要自己手写，我相信大家应该也都是能写出来的。
我也用代码实现了下，放在下面了。
#-*-coding:utf-8-*-
fromtypingimportList
deffind_K_max_number_method1(array:List[int],K:int)->int:
#首先对数组进行降序排序
sorted_array=sorted(array,reverse=True)
#注意下标是从0开始的，因此下标K-1是第K大元素
returnsorted_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大元素吗？
我用代码实现了下，你可以看下，同时用自己熟悉的语言实现下。
deffind_K_max_number_mathod2(array:List[int],K:int)->int:
#进行K轮，每次选择剩余元素的最大值
foriinrange(K):
index=i
#求解剩余元素最大值对应的下标
forjinrange(index+1,len(array)):
ifarray[j]>array[index]:
index=j
#剩余元素最大值和当前值进行交换
array[i],array[index]=array[index],array[i]
#返回下标为K-1的元素
returnarray[K-1]
这种方法相较于第一种方法，没有完全对数组进行排序，时间复杂度是
,
是数组的长度，空间复杂度是
，表面上看，这种方法比第一种方法好，但是由于K是一个不确定的值，如果比较小的话，这种方法是比较好的。
但是如果K约等于N的话，那么这种方法的时间复杂度就是
了，这个时候这种方法就还不如第一种方法呢。
所以这种方法的最好时间复杂度是
,最坏时间复杂度是
。
第三种方法：堆
接下来就进入到了第三种方法了，第三种方法是基于堆进行实现的。我们这里说的堆都是二叉堆，也就是只有左孩子结点和右孩子结点。
对堆不了解的小伙伴可以把堆理解成是一种特殊的二叉树，也就是完全二叉树，而且父子结点上的元素有大小关系限制。
父节点大于等于孩子节点的，称为大顶堆，父节点小于等于孩子节点的，称为小顶堆。
堆有很多应用，比较常见的有堆排序，优先队列，维护最值等等……
今天我们用到的功能就是维护最值，这里的最值不是简单的最大值或者最小值，而且前K大的值。
怎么理解呢？我们可以用一个长度为K的小顶堆来维护数组的前K个元素，然后让剩下的元素和堆顶元素（堆顶存储的是最小值）进行比较，如果当前元素大于堆顶元素，则进行交换。
这样，对数组进行遍历后，整个堆维护的就是数组的前K大元素，而且由于这是一个小顶堆，因此堆顶元素就是第K大元素。
实现的代码如下，你可以看下:
deffind_K_max_number_method3(array:List[int],K:int)->int:
#导入相关的package
importheapq
#首先获取数组的前K的元素，作为堆的初始值
heap=array[:K]
#将数组在线性时间内调整为堆，注意Python里面默认的就是小顶堆
heapq.heapify(heap)
foriinrange(K,len(array)):
#如果当前元素比堆顶元素大，就对堆进行调整
ifarray[i]>heap[0]:
heapq.heapreplace(heap,array[i])
returnheap[0]
这时候的时间复杂度你还知道吗？我们一起来看下。
首先对先K个元素进行建堆，时间复杂度是
然后对剩下的N-K个元素进行比较调整，最坏情况下，需要对剩下的所有元素都进行调整，这是时间复杂度就是
所以整体的时间复杂度就是
,空间复杂度是
.
堆在这方面的应用还有求中位数，也是很经典的一道面试题，感兴趣的小伙伴可以自己查下。
如果你觉得这道题到这就结束了，那你说明还是年轻了。
第四种方法：快速排序的方法
其实这道题还有第四种方法，那就是基于快速排序的方法。
可能现在你觉得这两者还没有任何关系，别着急，让我为你慢慢道来。
快排是基于分治的思想，简单说就是要想整个数组元素都有序，那么我可以找到一个主元，然后让左边的元素都比主元小，右边的元素都比主元大，这样只要左右区间都有序后，整个数组就有序了，那么左右区间如何有序呢，只要再选主元，让左右区间有序就可以了，直到细分后的左右区间长度为0，那么就不用再左右分了，也就结束了。
那么我们如何使用快排来解决这个问题呢？
我们来看快排哈，虽然我刚才上面讲了很多，但是总结来看就是两步，第一步，选主元；第二步，对左右进行递归排序。
选择主元结束后，主元所在的有序数组的位置就确定了，因为左边元素都比它小，右边的元素都比它大。所以它就是数组的第index大元素，index这里代表数组主元所对应的下标。如果index==K-1，那么这不就是我们要找的第K大元素，如果index<K-1,那么说明第K大元素在右区间，否则在左区间。
代码实现是这样的，可能有点难理解，需要你多读几遍。
deffind_K_max_number_method4(array:List[int],K:int)->int:
#首先确定边界
left,right=0,len(array)-1
#选定主元
partition=array[left]
whileleft<right:
#这里我们进行降序分区，也就是左区间值>主元，主元>右区间的值
whileleft<rightandarray[right]<=partition:
right-=1
array[left]=array[right]
whileleft<rightandarray[left]>partition:
left+=1
array[right]=array[left]
array[right]=partition
#如果right==K-1，目标已经找到了
ifright==K-1:
returnarray[right]
#如果right<K-1，那么在右区间查找第K-1-right大元素
elifright<K-1:
returnfind_K_max_number_method4(array[right+1:],K-1-right)
#否则在左区间查找第K大元素
else:
returnfind_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的优惠活动。
