NOIP 2007 统计数字 解题报告

　　这一题我的思路(应该)是O(nlogn)的，就是进行一趟快排加上对数组进行一次扫描。
　　快排直接调用库函数，扫描就是用j记录当前自然数，c记录当前自然数出现的次数，如果num[i]和j相同，c++；不同就输出j和c，然后j=num[i], c = 1。在循环结束后还要将最后一个自然数输出。
　　下面贴出代码：
#include <stdio.h>
int num[200000];

int com(const void a, const void b)
{
        return (int )a – (int )b;
}

int main(void)
{
        int n;
        int i, j, c;
        scanf("%d", &n);
        for(i = 0; i < n; i++){
                scanf("%d", &num[i]);
        }
        qsort(num, n, sizeof(int), com);
        j = num[0];
        //是num[0] 不是num[j] 
        c = 1;
        // c 要从1开始而不是0
        for(i = 1; i < n; i++){
                if(num[i] != j){
                        printf("%d %d\n", j, c);
                        j = num[i];
                        c = 1;
                        // c 要从1开始而不是0
                }else{
                        c++;
                }
        }
        printf("%d %d\n", j, c);
        return 0;
}