题目链接
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, greater> ，可以实现大根堆。
python 没有大根堆实现。
小根堆+手写
大根堆+手写
快速选择
代码
排序（c++）
classSolution { public: intfindKthLargest(vector<int>&nums, intk) { sort(nums.begin(), nums.end(), greater<int>() ); returnnums[k-1]; } };
小根堆+STL优先队列（c++）
classSolution { public: intfindKthLargest(vector<int>&nums, intk) { priority_queue<int, vector<int>, greater<int>>Q; for (autox : nums) { Q.push(x); while (Q.size() >k) Q.pop(); } returnQ.top(); } };
大根堆+STL优先队列（c++）
classSolution { public: intfindKthLargest(vector<int>&nums, intk) { priority_queue<int>Q; for (autox : nums) { Q.push(x); while (Q.size() >nums.size()-k+1) Q.pop(); } returnQ.top(); } };
小根堆+手写（c++）
classSolution { public: voidadjust(vector<int>&nums, intp, ints) { while (2*p+1<s) { intc1=2*p+1; intc2=2*p+2; intc= (c2<s&&nums[c2]<nums[c1]) ?c2 : c1; if (nums[c] <nums[p]) swap(nums[c], nums[p]); elsebreak; p=c; } } intfindKthLargest(vector<int>&nums, intk) { intn=nums.size(); for (inti=k/2-1; i>=0; --i) { adjust(nums, i, k); } for (inti=k; i<n; ++i) { if (nums[0] >=nums[i]) continue; swap(nums[0], nums[i]); adjust(nums, 0, k); } returnnums[0]; } };
大根堆+手写（c++）
classSolution { public: voidadjust(vector<int>&nums, intp, ints) { while (2*p+1<s) { intc1=2*p+1; intc2=2*p+2; intc= (c2<s&&nums[c2]>nums[c1]) ?c2 : c1; if (nums[c] >nums[p]) swap(nums[c], nums[p]); elsebreak; p=c; } } intfindKthLargest(vector<int>&nums, intk) { intn=nums.size(); for (inti= (n-k+1)/2-1; i>=0; --i) { adjust(nums, i, (n-k+1)); } for (inti= (n-k+1); i<n; ++i) { if (nums[0] <=nums[i]) continue; swap(nums[0], nums[i]); adjust(nums, 0, (n-k+1)); } returnnums[0]; } };
快速选择（c++）
classSolution { public: intpartition(vector<int>&nums, intl, intr) { intp=l+rand()%(r-l+1), m=l; swap(nums[p], nums[r]); for (inti=l; i<r; ++i) { if (nums[i] <nums[r]) { swap(nums[i], nums[m++]); } } swap(nums[m], nums[r]); returnm; } intquickSelect(vector<int>&nums, intl, intr, intk) { if (l==r) returnnums[l]; intm=partition(nums, l, r); if (k==m+1) returnnums[m]; if (k<m+1) returnquickSelect(nums, l, m-1, k); returnquickSelect(nums, m+1, r, k); } intfindKthLargest(vector<int>&nums, intk) { intn=nums.size(); srand((int)time(0)); returnquickSelect(nums, 0, n-1, n-k+1); } };
排序（python）
classSolution: deffindKthLargest(self, nums: List[int], k: int) ->int: nums.sort(reverse=True) returnnums[k-1]
小根堆+heapq（python）
classSolution: deffindKthLargest(self, nums: List[int], k: int) ->int: returnheapq.nlargest(k, nums)[-1]
小根堆+手写（python）
classSolution: deffindKthLargest(self, nums: List[int], k: int) ->int: defadjust(nums, p, s): while2*p+1<s: c1, c2=2*p+1, 2*p+2c=c2if (c2<sandnums[c2]<nums[c1]) elsec1ifnums[c] <nums[p]: nums[c], nums[p] =nums[p], nums[c] else: breakp=cn=len(nums) foriinrange(k//2-1, -1, -1): adjust(nums, i, k) foriinrange(k, n): ifnums[0] >=nums[i]: continuenums[0], nums[i] =nums[i], nums[0] adjust(nums, 0, k) returnnums[0]
大根堆+手写（python）
classSolution: deffindKthLargest(self, nums: List[int], k: int) ->int: defadjust(nums, p, s): while2*p+1<s: c1, c2=2*p+1, 2*p+2c=c2if (c2<sandnums[c2]>nums[c1]) elsec1ifnums[c] >nums[p]: nums[c], nums[p] =nums[p], nums[c] else: breakp=cn=len(nums) foriinrange((n-k+1)//2-1, -1, -1): adjust(nums, i, (n-k+1)) foriinrange((n-k+1), n): ifnums[0] <=nums[i]: continuenums[0], nums[i] =nums[i], nums[0] adjust(nums, 0, (n-k+1)) returnnums[0]
快速选择（python）
importrandomclassSolution: deffindKthLargest(self, nums: List[int], k: int) ->int: defpartition(nums, l, r): p, m=l+random.randint(0, r-l), lnums[p], nums[r] =nums[r], nums[p] foriinrange(l, r): ifnums[i] <nums[r]: nums[m], nums[i] =nums[i], nums[m] m+=1nums[m], nums[r] =nums[r], nums[m] returnmdefquickSelect(nums, l, r, k): ifl==r: returnnums[l] m=partition(nums, l, r) ifk==m+1: returnnums[m] ifk<m+1: returnquickSelect(nums, l, m-1, k) returnquickSelect(nums, m+1, r, k) n=len(nums) returnquickSelect(nums, 0, n-1, n-k+1)
参考资料
[1]
LeetCode 面试题 17.09. 第 k 个数: https://leetcode-cn.com/problems/kth-largest-element-in-an-array/
作者简介：godweiyang，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~
