返回信息流[【215. Kth Largest Element in an Array】](https://leetcode.com/problems/kth-largest-element-in-an-array/)
输入输出，示例：
Given `[3,2,1,5,6,4]` and `k = 2`, return 5.
这道题可以先用快排，再直接查找下标为`nums.length - k`的数即可，时间复杂度为O(n*logn)
如果用快速查找的方法，时间复杂度仅为O(n)，我的Java代码如下
```Java
public int findKthLargest(int[] nums, int k) {
return quickFind(nums, 0, nums.length - 1, k);
}
private int quickFind(int[] nums, int start, int end, int k) {
int provitKey = nums[start];
int left = start;
int right = end;
while (left < right) {
while (nums[right] > provitKey) right--;
nums[left] = nums[right];
while (left < right && nums[left] <= provitKey) left++;
nums[right] = nums[left];
}
if (end - left + 1 == k) return provitKey;
else if (end - left + 1 < k) return quickFind(nums, start, left - 1, k - (end - left + 1));
else return quickFind(nums, left + 1, end, k);
}
```
但是提交测试发现快排再查找的方法用时4ms，第二种方法快速查找竟然用时55ms，更耗时，挺奇怪的。求助一下原因
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #90676同步于 2016/8/1
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
请教一道leetcode中查找数组中第K大的数的题
Cabbage
2016/8/1镜像同步40 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
对于规模为n的数组
进行快速排序，其时间复杂度计算公式为：T(n) = 2*T(n/2) + n
同样规模的数组进行快速查找，其时间复杂度计算公式为：T(n) = T(n/2) + n
快速排序递归深度为logn，每层递归进行n次比较，所以复杂度是O(n*logn).
快速查找把n规模的数组分成两部分，后续只需要处理其中一部分。
顺着把式子写下去就是T(n) = n + n/2 + n/4 + n/8 + ... + 1 = 2n，快速查找最坏是O(n^2)，平均是O(n)呀
不至于那么多测试用例正好都是逆序求最小酱紫吧OrZ[ema19][ema2]
【 在 kit 的大作中提到: 】
: 你这个跟快排思路一样，为啥复杂度就是o(n)？
: 如果n个数完全逆序排列，求最小值(k=n)，你这个方法就退化到o(n^2)了吧。
虽然我也不知道应该怎么算，但觉得你的方法应该要乘个跟k相关的系数吧。
一般的oj都是以最慢的那组test最为用时。
【 在 Cabbage 的大作中提到: 】
: 对于规模为n的数组
: 进行快速排序，其时间复杂度计算公式为：T(n) = 2*T(n/2) + n
: 同样规模的数组进行快速查找，其时间复杂度计算公式为：T(n) = T(n/2) + n
: ...................
这种固定快速查找是能够被安排好的最坏情况破坏期望时间的。可是试试用随机快速查找，每层递归中在[start, end]中随机生成一个数i，之后swap(nums, i, start)。
并不能保证每次Partition可以将数组按比例划分成两个部分，所以最坏是O(n^2)的。
【 在 Cabbage 的大作中提到: 】
: 对于规模为n的数组
: 进行快速排序，其时间复杂度计算公式为：T(n) = 2*T(n/2) + n
: 同样规模的数组进行快速查找，其时间复杂度计算公式为：T(n) = T(n/2) + n
: ...................
provitKey要取随机的位置，递归判断的时候变成num[left]和num[l]，这样才不会退化
【 在 Yurnero 的大作中提到: 】
: 并不能保证每次Partition可以将数组按比例划分成两个部分，所以最坏是O(n^2)的。