题解 | #查找第K小数#小根堆+数组去重

#include <stdio.h>

//第x小的数可以用小根堆,先用较少的个数建立一个小根堆,然后插入新的结点,最终把数列插入完,然后用层次遍历的方法,遍历到第K即可
//但是如果选取的根堆规模不能够满足k,会找不到的,所以最笨的办法就是用n建立根堆

int in_num[1001];
int temp;


void HeadAdjust(int A[],int m,int len)
{
    //以元素m为根结点
    A[0] = A[m]; //把0位空出来用来交换
    for(int i=2*m;i<len;i*=2)
    {
        if(i<len&&A[i]>A[i+1])
        {
            i++;
        }
        if(A[0]<=A[i])
        {
            break; //已经符合小根堆了
        }
        else
        {
            A[m] = A[i];
            m=i; //继续往下筛选
        }
    }
    A[m] = A[0];
}

void BuildMinHeap(int A[],int len)
{
    for(int i=len/2;i>0;i--)
    {
        HeadAdjust(A,i,len);
    }
}

void HeadSort(int A[],int len)
{
    BuildMinHeap(A,len);
    for(int i=len;i>1;i--)
    {
        temp = A[i];
        A[i] = A[1];
        A[1] = temp; //相当于输出了堆顶元素
        HeadAdjust(A,1, i-1);
    }
}


int main() {
    int count,k;
    while(scanf("%d",&count) != EOF)
    {
        for(int i=1;i<=count;i++)
        {
            scanf("%d",&in_num[i]);
        }
        HeadSort(in_num,count);
        scanf("%d",&k);
        //现在要在有序序列里面去重
        int dest = count,cur=count-1;
        while(cur>0)
        {
            if(in_num[cur] != in_num[dest])
            {
                in_num[--dest] = in_num[cur--];
            }
            else
            {
                cur--;
            }
        }
        printf("%d",in_num[count-k+1]);
    }
    return 0;
}