【Leetcode】数组中的第k个最大元素

数组中的第k个最大元素

题目

思路

当需要从N个数当中选出最小的前K个数时，
如果采用传统排序，时间复杂度会达到O(N*N)
当N过大时，无法采用内排（即无法开辟过大的数组）

采用堆排序可以有效化解上述问题，找最小的前k个数建大堆，找最大的前k个数建小堆
创建一个容量为k的堆，之后依次将堆顶的数与N个数比较，大的放入堆顶，随后向下调整一次，再继续遍历比较

代码实现

void swap(int* p1,int* p2)
{
    int temp=*p1;
    *p1=*p2;
    *p2=temp;
}

void AdjustDown(int* a,int n,int root)//小堆向下调整算法
{
    int parent=root;
    int child=2*parent+1;
    while(child<n)
    {
        if(child+1<n && a[child+1]<a[child] )//child+1<n一定要放在&&前面
        {
            child++;
        }

        if(a[child]<a[parent])
        {
            swap(&a[child],&a[parent]);
            parent=child;
            child=2*parent+1;
        }
        else
        {
            break;
        }
    }
}
int findKthLargest(int* nums, int numsSize, int k) 
{
    
    int a[k];
    for(int i=0;i<k;i++)//将nums前k个数传到a中
    {
        a[i]=nums[i];
    }

    for(int i=(k-1-1)/2;i>=0;i--)//建小堆
    {
        AdjustDown(a,k,i);
    }

    for(int i=k;i<numsSize;i++)
    {
        if(nums[i]>a[0])
        {
            swap(&a[0],&nums[i]);
            AdjustDown(a,k,0);
        }
    }
    return a[0];
}