P1816 통계

P1816 통계 숫자 좋아, 곧 NOIP 시험이야. 나는 임시로 부처 다리를 안고 마음대로 233문제를 긁었어.오늘은 간단한 해시입니다.

#include
#include
typedef struct nature{
    int a;
    int sum;
    struct nature* next;
}N;//             
N hash[13];//    hash  
int S[10005];
int SUM=-1;

int comp(const void*a,const void*b)
{
    return *(int*)a-*(int*)b;
}

int add(int t)//     
{
    N* p;
    N* p1;
    p=&hash[t%13];
    while(1)
    {
        if(t==p->a)
        {
            p->sum++;   
            return 0;
        }
        else
        {
            if(p->next!=0)
            p=p->next;
            else
            break;
        }   
    }
    if(p->next==0)
    {
        p1=(N*)malloc(sizeof(N));
        p1->a=t;
        p1->sum=1;
        p1->next=0;
        p->next=p1;
    }
    return 0;
}

int search(int a)//          
{
    N* p;
    p=hash[a].next;
    while(p!=0)
    {
        SUM++;
        S[SUM]=p->a;
        p=p->next;
    }
    return 0;
}

int read(int t)//  
{
    N* p;
    p=hash[t%13].next;
    while(p->a!=t)
    p=p->next;
    printf("%d %d 
",t,p->sum);
    return 0;
}

int main()
{
    int n;
    int i,temp;
    scanf("%d",&n);

    for(i=0;i<13;i++)
    {
        hash[i].next=0;
        hash[i].a=-1; 
        hash[i].sum=-1;
    }


    for(i=1;i<=n;i++)
    {
        scanf("%d",&temp);
        add(temp);
    }

    for(i=0;i<13;i++)
    search(i);

    qsort(S,SUM+1,sizeof(int),comp);//     “+1”，        SUM，    SUM+1

    for(i=0;i<=SUM;i++)
    read(S[i]);
    return 0;
}

라라, 아주 간단합니다. 최대 10000개의 숫자가 있고 최대 1.5*10^9이기 때문에 비교할 수 없으니 해시로 분류하세요...다시 선형 테이블 처리를 통해 모순 공간의 크기는 O(N)이고 시간 복잡도(N^2)(즉 모든 원소가 13에 대한 여분의 값을 동일하게 구한 다음에 모두 함께 배열한다...)