# 题目描述

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.

# 我的解法

## 实现代码

Runtime: 12 ms, faster than 77.71% of C++ online submissions for Kth Largest Element in an Array.
Memory Usage: 9.2 MB, less than 89.39% of C++ online submissions for Kth Largest Element in an Array.

# 高票解法

C++中排序的时间复杂度为O(NlogN)，如果使用优先队列，对于插入一个大小为k的优先队列插入N次，时间复杂度为O(Nlogk)也可以使用C++中的priority_queue优先队列，默认是大顶堆。

## 实现代码

Runtime: 8 ms, faster than 97.45% of C++ online submissions for Kth Largest Element in an Array.
Memory Usage: 9.5 MB, less than 40.91% of C++ online submissions for Kth Largest Element in an Array.

## 代码分析

Runtime: 8 ms, faster than 97.45% of C++ online submissions for Kth Largest Element in an Array.
Memory Usage: 9.5 MB, less than 33.33% of C++ online submissions for Kth Largest Element in an Array.