CSP201503-2：数字排序

引言：CSP（http://www.cspro.org/lead/application/ccf/login.jsp）是由中国计算机学会（CCF）发起的"计算机职业资格认证"考试，针对计算机软件开发、软件测试、信息管理等领域的专业人士进行能力认证。认证对象是从事或将要从事IT领域专业技术与技术管理人员，以及高校招考研究生的复试对象。

 

• 问题描述

　　给定n个整数，请统计出每个整数出现的次数，按出现次数从多到少的顺序输出。

• 输入格式

　　输入的第一行包含一个整数n，表示给定数字的个数。

　　第二行包含n个整数，相邻的整数之间用一个空格分隔，表示所给定的整数。

• 输出格式

　　输出多行，每行包含两个整数，分别表示一个给定的整数和它出现的次数。按出现次数递减的顺序输出。如果两个整数出现的次数一样多，则先输出值较小的，然后输出值较大的。

• 样例输入

  12

  5 2 3 3 1 3 4 2 5 2 3 5

• 样例输出

  3 4

  2 3

  5 3

  1 1

  4 1

• 评测用例规模与约定

  1 ≤ n ≤ 1000，给出的数都是不超过1000的非负整数。

 

• 源代码

# include <stdio.h>

# include <stdlib.h>

# include <memory.h>

# include <algorithm>

 

using namespace std;

 

struct group {

    int num; //数字

    int times; //出现的次数

};

 

//比较函数

bool cmp(group a, group b)

{

    if (a.times == b.times)

    {

        return a.num < b.num;

    }

    return a.times > b.times;

}

 

int main(void)

{

    int n; //数字个数

    scanf("%d", &n);

    

    group *pInput = (group *)malloc(sizeof(group) * n);

    //初始化输入数组

    for (int i = 0; i < n; i++)

    {

        pInput[i].num = -1;

        pInput[i].times = 0;

    }

    

    int length = 0;

    for (int i = 0; i < n; i++)

    {

        int tempNum;

        scanf("%d", &tempNum);

        int j = 0;

        int sign = 1;

        while (j < length)

        {

            //如果输入的数字已经存在，直接在time上+1

            if (tempNum == pInput[j].num)

            {

                pInput[j].times += 1;

                sign = 0;

                break;

            }    

            j++;        

        }

        if (sign)

        {

            //如果输入的数字不存在，令num = tmepNum

            pInput[length].num = tempNum;

            pInput[length].times = 1;

            length += 1;

        }

    }

    sort(pInput, pInput + length, cmp);

    

    for (int i = 0; i < length; i++)

    {

        printf("%d ", pInput[i].num);

        printf("%d\n", pInput[i].times);

    }

      

    

    free(pInput);

    

    return 0;

}