【每日算法Day 82】面试经典题：求第K大数，我写了11种实现，不来看看吗？

【每日算法Day 82】面试经典题：求第K大数，我写了11种实现，不来看看吗？

题目链接

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++）

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

小根堆+STL优先队列（c++）

class Solution {public: int findKthLargest(vector& nums, int k) { priority_queue, greater> 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& nums, int k) { priority_queue 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& nums, int p, int s) { while (2*p+1 < s) { int c1 = 2*p+1; int c2 = 2*p+2; int c = (c2& 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& nums, int p, int s) { while (2*p+1 < s) { int c1 = 2*p+1; int c2 = 2*p+2; int c = (c2nums[c1]) ? c2 : c1; if (nums[c] > nums[p]) swap(nums[c], nums[p]); else break; p = c; } } int findKthLargest(vector& 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& 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& 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& 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= 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 (c2nums[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 randomclass 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)

参考资料

[1]

LeetCode 面试题 17.09. 第 k 个数: ​​https://leetcode-cn.com/problems/kth-largest-element-in-an-array/​​

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。