直方图（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;  }

(adsbygoogle = window.adsbygoogle || []).push({});