题目链接
LeetCode 215. 数组中的第K个最大元素[1]
题目描述
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例1
输入： [3,2,1,5,6,4] 和 k = 2 输出： 5
示例2
输入： [3,2,3,1,2,4,5,5,6] 和 k = 4 输出： 4
解释：
- 你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
题解
排序
对数组从大到小排序，取第 个元素。
或者从小到大排序，取第 个元素。
小根堆+库函数
c++ 自带 priority_queue<int> ，可以实现小根堆。
python 自带 heapq ，可以实现小根堆，同时还自带 nlargest 函数可以直接求出前 大元素。
然后维护一个大小为 的小根堆，保存最大的 个数，堆顶就是第 大的数。新元素入堆，如果堆中元素个数大于 ，就将堆顶元素出堆。
大根堆+库函数
c++ 自带 priority_queue<int, vector<int>, greater<int>> ，可以实现大根堆。
python 没有大根堆实现。
然后维护一个大小为 的大根堆，保存最小的 个数，堆顶就是第 小的数，即第 大的数。新元素入堆，如果堆中元素个数大于 ，就将堆顶元素出堆。
小根堆+手写
利用原地算法，直接将原数组当作一个小根堆。
首先对前 个元素建立初始堆。然后遍历后面的元素，如果大于堆顶元素的话，就和堆顶元素交换位置，并调整堆。
小根堆大小始终为 。
大根堆+手写
利用原地算法，直接将原数组当作一个大根堆。
首先对前 个元素建立初始堆。然后遍历后面的元素，如果小于堆顶元素的话，就和堆顶元素交换位置，并调整堆。
大根堆大小始终为 。
快速选择
思想类似于快速排序，首先随机选取一个元素 ，然后将区间内元素比 小的都放在 左边，比 大的都放在 右边。
然后看 的下标 ，如果 ，那就说明 就是第 小（第 大）的元素，直接返回即可。否则如果 ，那就说明第 大元素在 的右边区间内，递归寻找即可。否则就在左边区间，递归寻找。
代码
排序（c++）
class Solution { public: int findKthLargest(vector<int>& nums, int k) { sort(nums.begin(), nums.end(), greater<int>()); return nums[k-1]; } };
小根堆+STL优先队列（c++）
class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int, vector<int>, greater<int>> Q; for (auto x : nums) { Q.push(x); while (Q.size() > k) Q.pop(); } return Q.top(); } };
大根堆+STL优先队列（c++）
class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int> Q; for (auto x : nums) { Q.push(x); while (Q.size() > nums.size()-k+1) Q.pop(); } return Q.top(); } };
小根堆+手写（c++）
class Solution { public: void adjust(vector<int>& nums, int p, int s) { while (2*p+1 < s) { int c1 = 2*p+1; int c2 = 2*p+2; int c = (c2<s && nums[c2]<nums[c1]) ? c2 : c1; if (nums[c] < nums[p]) swap(nums[c], nums[p]); else break; p = c; } } int findKthLargest(vector<int>& nums, int k) { int n = nums.size(); for (int i = k/2-1; i >= 0; --i) { adjust(nums, i, k); } for (int i = k; i < n; ++i) { if (nums[0] >= nums[i]) continue; swap(nums[0], nums[i]); adjust(nums, 0, k); } return nums[0]; } };
大根堆+手写（c++）
class Solution { public: void adjust(vector<int>& nums, int p, int s) { while (2*p+1 < s) { int c1 = 2*p+1; int c2 = 2*p+2; int c = (c2<s && nums[c2]>nums[c1]) ? c2 : c1; if (nums[c] > nums[p]) swap(nums[c], nums[p]); else break; p = c; } } int findKthLargest(vector<int>& nums, int k) { int n = nums.size(); for (int i = (n-k+1)/2-1; i >= 0; --i) { adjust(nums, i, (n-k+1)); } for (int i = (n-k+1); i < n; ++i) { if (nums[0] <= nums[i]) continue; swap(nums[0], nums[i]); adjust(nums, 0, (n-k+1)); } return nums[0]; } };
快速选择（c++）
class Solution { public: int partition(vector<int>& nums, int l, int r) { int p = l+rand()%(r-l+1), m = l; swap(nums[p], nums[r]); for (int i = l; i < r; ++i) { if (nums[i] < nums[r]) { swap(nums[i], nums[m++]); } } swap(nums[m], nums[r]); return m; } int quickSelect(vector<int>& nums, int l, int r, int k) { if (l == r) return nums[l]; int m = partition(nums, l, r); if (k == m+1) return nums[m]; if (k < m+1) return quickSelect(nums, l, m-1, k); return quickSelect(nums, m+1, r, k); } int findKthLargest(vector<int>& nums, int k) { int n = nums.size(); srand((int)time(0)); return quickSelect(nums, 0, n-1, n-k+1); } };
排序（python）
class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: nums.sort(reverse=True) return nums[k-1]
小根堆+heapq（python）
class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: return heapq.nlargest(k, nums)[-1]
小根堆+手写（python）
class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: def adjust(nums, p, s): while 2*p+1 < s: c1, c2 = 2*p+1, 2*p+2 c = c2 if (c2<s and nums[c2]<nums[c1]) else c1 if nums[c] < nums[p]: nums[c], nums[p] = nums[p], nums[c] else: break p = c n = len(nums) for i in range(k//2-1, -1, -1): adjust(nums, i, k) for i in range(k, n): if nums[0] >= nums[i]: continue nums[0], nums[i] = nums[i], nums[0] adjust(nums, 0, k) return nums[0]
大根堆+手写（python）
class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: def adjust(nums, p, s): while 2*p+1 < s: c1, c2 = 2*p+1, 2*p+2 c = c2 if (c2<s and nums[c2]>nums[c1]) else c1 if nums[c] > nums[p]: nums[c], nums[p] = nums[p], nums[c] else: break p = c n = len(nums) for i in range((n-k+1)//2-1, -1, -1): adjust(nums, i, (n-k+1)) for i in range((n-k+1), n): if nums[0] <= nums[i]: continue nums[0], nums[i] = nums[i], nums[0] adjust(nums, 0, (n-k+1)) return nums[0]
快速选择（python）
import random class Solution: def findKthLargest(self, nums: List[int], k: int) -> int: def partition(nums, l, r): p, m = l+random.randint(0, r-l), l nums[p], nums[r] = nums[r], nums[p] for i in range(l, r): if nums[i] < nums[r]: nums[m], nums[i] = nums[i], nums[m] m += 1 nums[m], nums[r] = nums[r], nums[m] return m def quickSelect(nums, l, r, k): if l == r: return nums[l] m = partition(nums, l, r) if k == m+1: return nums[m] if k < m+1: return quickSelect(nums, l, m-1, k) return quickSelect(nums, m+1, r, k) n = len(nums) return quickSelect(nums, 0, n-1, n-k+1)
