# 215. Kth Largest Element in an Array 数组中的第K个最大元素

@TOC

## # 题目描述

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.

## # 解题方法

### # 方法一：移除最大值

``````In [1]: a = [1,2,3,3,3,3]

In [2]: a.remove(3)

In [3]: a
Out[3]: [1, 2, 3, 3, 3]

In [4]: a.remove(3)

In [5]: a
Out[5]: [1, 2, 3, 3]

``````

``````class Solution(object):
def findKthLargest(self, nums, k):
"""
:type nums: List[int]
:type k: int
:rtype: int
"""
for i in range(k - 1):
nums.remove(max(nums))
return max(nums)
``````

### # 方法二：排序

``````class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
return nums[nums.size() - k];
}
};
``````

### # 方法三：大顶堆

``````class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
priority_queue<int> q;
for (int n : nums) {
q.push(n);
}
int res = 0;
while (k--) {
res = q.top(); q.pop();
}
return res;
}
};
``````

## # 日期

2018 年 2 月 5 日 2018 年 12 月 23 日 —— 周赛成绩新高