直方图（histogram.cpp）

【题目描述】

给定一个非负整数数组，统计里面每一个数的出现次数。我们只统计到数组里面最大的数。

假设Fmax(Fmax<10000)是数组里最大的数，那么我们只统计{0，1，2...Fmax}里每个数出现的次数。

【输入描述】

第一行n个数组的大小，1<=n<=10000

紧接着一行是数组的n个元素。

【输出描述】

按顺序输出每个数的出现次数，一行一个数。如果没有出现，则输出0。对于例子中的数组，最大的数是3，因此我们只统计{0，1，2，3}的出现频数。

【样例输入】

5
1 1 2 3 1

【样例输出】

0
3
1
1

【题目分析】

• 非常经典的桶排使用方法，a[x]++操作就能完成排序工作

• 统计只到max每个数出现的次数，只需要我们在计算过程中把最大数统计出来即可。

【参考代码1】

#include<bits/stdc++.h>
using namespace std;

int main()
{
    int n;
    cin>>n;
    int a[10001];//定义数组
    int  Fmax=-1;//定义最大的数
    for(int i=0; i<n; i++)
    {
        cin>>a[i];
        if(Fmax<=a[i])
            Fmax=a[i];//找出最大的数
    }
    int b[10001];//声明计数数组
    memset(b,0, sizeof(b));//初始化数组
    for(int i=0; i<n; i++)
    {
        b[a[i]]++;//统计出现的次数
    }
    for(int i=0; i<=Fmax; i++)
    {
        cout<<b[i]<<endl;
    }

    return 0;
}

【参考代码2】

#include<iostream>
using namespace std; 
int main() 
{
    int n,x;
    int a[10001]={0};
    int max=-9999,flag;
    int i;
    
    /*桶排的思想*/
    
    cin>>n;//输入数组大小n
    for(i=1;i<=n;i++)
    {
        cin>>x;//输入元素
    	a[x]++;
        if(x>max)
            max=x;//记录最大值
    }
    for(i=0;i<=max;i++)//输出到max为止的频数
    	cout<<a[i]<<endl;
    
    return 0;
}