# LeetCode215. Kth Largest Element in an Array（快速排序）

## LeetCode215. Kth Largest Element in an Array（快速排序）

• Medium
• Accepted：310,190
• Submissions：684,666

Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.

### Example 1:

Input: [3,2,1,5,6,4] and k = 2
Output: 5

### Example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

### Note:

You may assume k is always valid, 1 ≤ k ≤ array's length.

### 链接

https://leetcode.com/problems/kth-largest-element-in-an-array/

### 题解

• 直接sort一下，时间复杂度$O(nlogn)$
• 利用快速排序找基准值pivot位置的思想，从大到小排序，在基准值pivot左边的都大于pivot，在基准值pivot右边的都小于pivot，第k大元素的位置为k-1，如果基准值的位置pos等于k-1那么直接返回nums[pos]，如果pos大于k-1那么往左边找，pos小于k-1则往右边找，找到合适的基准值位置那么答案就出来了，平均时间复杂度$T(n) = T(n/2) + n$，即$O(n)$

### 代码

• Runtime: 8 ms, faster than 72.24% of C++ online submissions for Kth Largest Element in an Array.
• Memory Usage: 1.1 MB, less than 28.15% of C++ online submissions for Kth Largest Element in an Array.
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int len = nums.size();
sort(nums.begin(), nums.end());
return nums[len-k];
}
};
• Runtime: 40 ms, faster than 13.55% of C++ online submissions for Kth Largest Element in an Array.
• Memory Usage: 1.1 MB, less than 81.46% of C++ online submissions for Kth Largest Element in an Array.
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
int len = nums.size();
int left = 0, right = len - 1;
while (true)
{
int pos = partition(nums, left, right);
if (pos == k - 1) // pos位置为第k大数的位置直接返回
return nums[pos];
if (pos > k - 1) // pos位置在k-1的右边，往左边找
right = pos - 1;
else if (pos < k - 1) // pos位置在k-1的左边，往右边找
left = pos + 1;
}
}

// 找到基准位置，挖空法
int partition(vector<int>& nums, int low, int high)
{
int ret = low;
int pivot = nums[ret];
for (int i = low + 1; i <= high; ++i)
{
if (nums[i] > pivot)
{
nums[ret] = nums[i];
nums[i] = nums[++ret];
}
}
nums[ret] = pivot;
return ret;
}
};

The end.
2019年2月3日 星期日