【每日算法Day 82】面试经典题：求第K大数，我写了11种实现，不来看看吗？-阿里云开发者社区

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

2022-06-25 203

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介： 在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

题目链接

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，知乎同名，华东师范大学计算机系硕士在读，方向自然语言处理与深度学习。喜欢与人分享技术与知识，期待与你的进一步交流~