欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

LeetCode 215 -- 数组中的第K个最大元素 ( Kth Largest Element in an Array ) ( C语言版 )

程序员文章站 2022-04-25 12:30:08
...

题目描述 : 

LeetCode 215 -- 数组中的第K个最大元素 ( Kth Largest Element in an Array ) ( C语言版 )

解题思路 : 解法一  : 看到题目第一时间就想到了 , 使用堆 , 这里可以直接建一个大小为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];
}