# 215. Kth Largest Element in an Array / Medium

Given an integer array nums and an integer k, return the kth largest element in the array.

Note that it is the kth largest element in the sorted order, not the kth distinct element.

## Example 1:

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

## Example 2:

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

## Constraints:

• 1 <= k <= nums.length <= 10^4
• -10^4 <= nums[i] <= 10^4

# Solution 1: Sort

## 效能

### Complexity

• Time Complexity: O(NlogN)
• Space Complexity: O(1)

### LeetCode Result

• Runtime: 4 ms
• Memory Usage: 10 MB

# Solution 2: Heap

## 效能

### Complexity

• Time Complexity: O(NlogK)
• Space Complexity: O(NlogK)

### LeetCode Result

• Runtime: 8 ms
• Memory Usage: 10 MB

# Solution 3: C++ STL: partial_sort()

## 思路

partial_sort() 底層的實作是 Heapselect，即 Solution 2 的解法。

## 效能

### Complexity

• Time Complexity: O(NlogK)
• Space Complexity: O(NlogK)

### LeetCode Result

• Runtime: 8 ms
• Memory Usage: 10 MB

# Solution 4: C++ STL: nth_element()

## 思路

nth_element() 的底層是 Quickselect，他會將第 n 大的元素放在第 n-1 位置，其前後則不保證排序。

## 效能

### Complexity

• Time Complexity: O(N)
• Space Complexity: O(1)

### LeetCode Result

• Runtime: 3 ms
• Memory Usage: 9.9 MB

# Solution 5: Quickselect / Hoare’s selection

## 效能

### Complexity

• Time Complexity: O(N)
• Space Complexity: O(1)

### LeetCode Result

• Runtime: 0 ms
• Memory Usage: 9.9 MB