本文主要是介绍寻找第K大（借用快排思想），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
1.题目：牛客网 NC88 （寻找第K大）
描述
有一个整数数组，请你根据快速排序的思路，找出数组中第K大的数。
给定一个整数数组a,同时给定它的大小n和要找的K(1<K<n)，请返回第k大的数(包括重复的元素，不用去重)，保证答案存在。要求时间复杂度O(n)示例1
输入：
[1,3,5,2,2],5,3
返回值：
2
2.解题思路
这题给了提示，可以借用快排的思想。同时要注意对事件复杂度的要求是O(n)。
对于快排不熟悉的，建议看下我的这篇博文：快速排序详细讲解和代码实现
先给大家介绍第一种思路：先对A进行快速排序（从小到大），然后返回第K大的数
class Solution {
public:int findKth(vector<int> a, int n, int K) {// write code herequickSort(a,0,n-1);return a[n-K];}void quickSort(vector<int> &A,int low,int high){if(low<high){int pivotpos=Partition(A,low,high);quickSort(A,low,pivotpos-1);quickSort(A,pivotpos+1,high);}}int Partition这篇关于寻找第K大（借用快排思想）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
