LeetCode 215 -- 数组中的第K个最大元素 ( Kth Largest Element in an Array ) ( C语言版 )
程序员文章站
2022-04-25 12:30:08
...
题目描述 :
解题思路 : 解法一 : 看到题目第一时间就想到了 , 使用堆 , 这里可以直接建一个大小为k的小堆 , 然后将数组中元素依次与堆顶元素比较 , 比堆顶元素大入堆 , 并更新堆顶元素 , 比堆顶元素小则不处理 , 当数组遍历完之后 , 第k个最大元素就是堆顶元素 , 该方法时间复杂度为 O(n) , 但是由于还没学到java ,不可能现撸一个小堆出来 ,
解法二 : 使用插入排序 , 虽然复杂度较高 ,但是也能解决问题
插入排序详解 ( 传送门 ) -- https://blog.csdn.net/ds19980228/article/details/82589860
代码如下 :
int findKthLargest(int* nums, int ns, int k) {
int end=0;
for(int i=0;i<ns-1;i++){
end=i+1;
int tmp=nums[end];
if(nums[end]>nums[i]){
while(end>0&&tmp>nums[end-1]){
nums[end]=nums[end-1];
end--;
}
}
nums[end]=tmp;
}
return nums[k-1];
}
上一篇: 华为:Access、Hybrid和Trunk三种模式的理解
下一篇: 持续集成与持续交付与持续部署