蓝桥杯---数组里面的第k大的元素（leetcode第215题）题解

1.题目重现

之前是对于数组排序，找出来这个数组里面的最大的或者是最小的元素，但是这个题目是找出来排序之后的这个数组里面的第k大的元素；

2.案例说明

我觉得这个题目上面的解释足够清楚，这个案例也就没什么好说的，其实是很容易理解的:

就是给我们传递进来一个数组，我们需要在这个数组里面的这么多个数字里面找到第K大的元素；

3.思路介绍

思路就是数组分为三块，随机的进行基准元素的选择：

其实现在回想起来，这个思路贯穿了始终，从我们的最开始的那个颜色的分类问题，就是0,1,2我们是有基准元素的，到后来的这个快速排序算法，再到现在的这个topK问题，也就是最大的第K个元素，实际上我们都是利用的这个数组划分为三块的这个思想；

因为我们是把这个数组划分了三个部分，也就是数组分为三块，因此我们的这个topK最首要的问题就是需要知道我们找的这个topk元素在我们的这个数组里面的哪一个位置，也就是三块里面的那一块里面；

我们的思路就是下面的这个里面写的a,b,c就是分别计算出来每一块里面的元素的数据个数，和我们的这个K进行比较，确定这个topK元素在我们的数组里面的什么位置

因为这个按照数组分三块快排之后，这个数组是升序的，所以我们找的是topK,应该是从这个数组的大元素开始找，我们首先让这个c和k进行比较，如果c>=k，这个就意味着我们的这个元素就是在第三块里面的，我们在这个right,r区间里面去寻找第k大的元素就可以了；

以此类推，如果是在第二块里面的话，因为全部都是等于我们的key，直接返回这个基准元素就可以了；

上面的两个情况都不满足的情况下，这个时候就需要在我们的最左边的那一块里面去找地k-b-c大的元素；

4.代码分析

下面的这个findKlargest函数就是去寻找我们的数组里面的这个最大的元素

• 总体来看，就是调用qsort函数，然后我们去实现这个函数，函数里面的数组分三块的时候涉及到了数据元素的交换，然后我们实现了一个swap函数；
• 其实这个里面最主要的就是我们的qsort这个函数，这个函数里面主要就是包含了三个步骤，分别是我们的随机选择基准元素，数组分三块，分类讨论；
• 随机选择基准元素是为了让这个时间复杂度降低到最少，这个具体原理可以参考《算法导论》这本书籍；数组分三块，已经不是我们第一次使用了，之前的那个快排里面进行了详细的介绍（可参考我之前的文章），分类讨论，就是确定我们的这个topk位于我们的数组分三块；里面的哪一块里面；