问题 B: 分组统计
分組統(tǒng)計(jì)
問題 B: 分組統(tǒng)計(jì)時(shí)間限制: 1 Sec 內(nèi)存限制: 32 MB
提交: 416 解決: 107
[提交][狀態(tài)][討論版][命題人:外部導(dǎo)入]
題目描述
先輸入一組數(shù)，然后輸入其分組，按照分組統(tǒng)計(jì)出現(xiàn)次數(shù)并輸出，參見樣例。
輸入
輸入第一行表示樣例數(shù)m，對(duì)于每個(gè)樣例，第一行為數(shù)的個(gè)數(shù)n，接下來兩行分別有n個(gè)數(shù)，第一行有n個(gè)數(shù)，第二行的n個(gè)數(shù)分別對(duì)應(yīng)上一行每個(gè)數(shù)的分組，n不超過100。
輸出
輸出m行，格式參見樣例，按從小到大排。
樣例輸入
1 7 3 2 3 8 8 2 3 1 2 3 2 1 3 1樣例輸出
1={2=0,3=2,8=1} 2={2=1,3=0,8=1} 3={2=1,3=1,8=0}思考
http://codeup.cn/problem.php?cid=100000582&pid=1
這個(gè)是典型的哈希算法了。
這個(gè)樣例是統(tǒng)計(jì)每組數(shù)字里面各數(shù)字（出現(xiàn)在第一行的數(shù)字，這一次是3,2,8）的個(gè)數(shù)。
所以每一組數(shù)字要個(gè)數(shù)組3，記錄2,3,8的個(gè)數(shù)
先搞一個(gè)在n個(gè)數(shù)字第一次出現(xiàn)時(shí)的數(shù)組num，記錄那些數(shù)字出現(xiàn)了，出現(xiàn)了幾次，以該數(shù)字為下標(biāo)的數(shù)組值++，那這個(gè)數(shù)組大小應(yīng)該是很大的啊 。
再來就是分組了，再來一個(gè)數(shù)組zu,以上一行出現(xiàn)過數(shù)字為下標(biāo)，值為所分的組。
n不超過100。怎么表示這種性質(zhì)呢？結(jié)構(gòu)體？一個(gè)整型，記錄其在第一行的n個(gè)數(shù)里的出現(xiàn)次數(shù)，再來一個(gè)數(shù)組，記錄自己在不同組的出現(xiàn)次數(shù)。
組數(shù)肯定要小于n
本地實(shí)現(xiàn)
這問題幾個(gè)月之前就遇到過了。
#include <stdio.h> #include <stdlib.h> #include <stdbool.h> //#include <limits.h> #define maxn 10005 int cmp(const void*a, const void*b){return *(int*)a - *(int*)b;//升序 } int main(){int m;while(scanf("%d", &m) != EOF){while(m--){int n;scanf("%d", &n);int cishu[maxn][n+1]= {0};//int temp[n+1] = INT_MAX;int temp[n+1] = {0};for(int i = 1; i <= n; i++){scanf("%d", &temp[i]);cishu[temp[i]][0]++;//將第一行數(shù)讀入數(shù)組temp，并且在相應(yīng)行第0列記錄出現(xiàn)在第一行出現(xiàn)次數(shù) }int zu[n+1] = {0}, num = 0, kzu[n+1] = {0};for(int i = 1; i <= n; i++) {scanf("%d",&zu[i]);kzu[zu[i]]++;cishu[temp[i]][zu[i]]++; }/*二維數(shù)組里行代表這個(gè)數(shù)，列代表該行對(duì)應(yīng)數(shù)在某組里出現(xiàn)的次數(shù)*/for(int i = 1; i <= n; i++) {if(kzu[i] > 0)num++;}//num記錄分的組的個(gè)數(shù)/*該對(duì)第一行的n個(gè)數(shù)按大小排序了*/qsort(temp+1, n, sizeof(temp[0]), cmp);/*for(int i = 1; i <= n; i++){printf("%d\n", temp[i]);}//排序正確*//*剔除重復(fù)項(xiàng)，建立新數(shù)組*/int newtemp[n+1], newxu = 2;newtemp[1] = temp[1];for(int i = 2; i <= n; i++) {if(temp[i] != temp[i-1])//if語句的括號(hào)后面跟分號(hào)，編譯器竟然沒error newtemp[newxu++] = temp[i]; }/*for(int i = 1; i < newxu; i++){printf("%d\n", newtemp[i]);}//剔除重復(fù)項(xiàng)，新數(shù)組正確*/for(int j = 1; j <= num; j++) {printf("%d={", j); //第j組for(int i = 1; i < newxu; i++){printf("%d=%d", newtemp[i], cishu[newtemp[i]][j]); if(i < newxu-1)printf(","); }printf("}\n");} } }return 0; }別人的代碼1-二維數(shù)組
s066 Problem B 分組統(tǒng)計(jì) - CSDN博客 https://blog.csdn.net/fantasydreams/article/details/79114487
#include <iostream> #include <fstream> #include <algorithm> using namespace std; const int MaxN = 102; int main() { #ifdef _DEBUGifstream cin("data.txt"); #endif // _DEBUG//利用鏈表散列進(jìn)行統(tǒng)計(jì)，這里用二維數(shù)組模擬int m, n;while (cin >> m){while (m--){int Table[MaxN][MaxN] = {0}, classFlag[MaxN] = {false}, Class[MaxN], ClaN = 0, Num[MaxN], tmp, NumUi[MaxN], N = 0;cin >> n;for (int i = 0; i < n; ++i)cin >> Num[i];//讀入第一行所有數(shù) for (int i = 0; i < n; ++i){cin >> tmp;if (!classFlag[tmp]){classFlag[tmp] = true;Class[ClaN++] = tmp;//該組的序號(hào)第一次出現(xiàn)時(shí)，記錄進(jìn)來 }Table[tmp][Table[tmp][MaxN - 1]++] = Num[i];//建立這個(gè)表，第幾組就是第幾行 ，避免了數(shù)組越界 }//該數(shù)是第幾組存進(jìn)第幾行的，存進(jìn)哪一列呢？從第1列，開始存，該行最后一列記錄了該組的數(shù)字個(gè)數(shù) sort(Class, Class + ClaN);//組序號(hào)排序 ，ClaN記錄組的個(gè)數(shù) sort(Num, Num + n);//第一行數(shù)字排序 /*剔除重復(fù)項(xiàng)，建立新數(shù)組*/for (int i = 0; i < n; ++i){if (N == 0 || Num[i] != NumUi[N-1]){NumUi[N++] = Num[i];}}for (int k = 0; k < ClaN; ++k){printf("%d={", Class[k]);/*組號(hào)*/for (int h = 0; h < N; ++h)/*按第一行數(shù)字順序*/{ /*查詢，如果出現(xiàn)相同的，則數(shù)字加1*/int c = 0, j = 0;for (; j < Table[Class[k]][MaxN - 1]; ++j){if (Table[Class[k]][j] == NumUi[h])++c;}printf("%d=%d", NumUi[h], c);if (h < N-1)printf(",");}printf("}\n");}}}#ifdef _DEBUGcin.close();system("pause"); #endif // _DEBUGreturn 0; }別人的代碼2-散列
C/C++[codeup 2066]分組統(tǒng)計(jì) - CSDN博客 https://blog.csdn.net/u014281392/article/details/80841162
C++ STL算法系列4---unique , unique_copy函數(shù) - 夏雪冬日 - 博客園 https://www.cnblogs.com/heyonggang/archive/2013/08/07/3243477.html
這里比較重要的是，取得容器內(nèi)最大值，防止二維數(shù)組越界問題。
防止越界的散列
C++ STL之min_element()與max_element（）（取容器中的最大最小值） - Angel_Kitty - 博客園 https://www.cnblogs.com/ECJTUACM-873284962/p/6734225.html
#include<iostream> #include<algorithm> using namespace std; bool cmp(int a,int b) { return a<b; // return a>b; } int main() { int num[]={2,3,1,6,4,5}; cout<<"最小值是 "<<*min_element(num,num+6)<<endl; //默認(rèn)升序 cout<<"最大值是 "<<*max_element(num,num+6)<<endl; cout<<"最小值是 "<<*min_element(num,num+6,cmp)<<endl; //可以修改為 return a>b;改降序 cout<<"最大值是 "<<*max_element(num,num+6,cmp)<<endl; return 0; }關(guān)于c語言初始化的問題
C/C++數(shù)組初始化的一些誤區(qū) - CSDN博客 https://blog.csdn.net/u014417133/article/details/77185009
也就是說，要置零，使用memset最好了。
memset(cur,0,sizeof(cur))
AC代碼
#include <iostream> #include <algorithm> //max_element,unique_copy #include <cstring> #include <vector> using namespace std; int main() {int M;while(cin>>M) {while (M--) {int N; //輸入數(shù)據(jù)的個(gè)數(shù)cin >> N;int nums[N], cls[N]; //數(shù)據(jù)和類別for (int i = 0; i < N; i++)cin >> nums[i];for (int i = 0; i < N; i++)cin >> cls[i];// 數(shù)據(jù)的最大值和類別int max_cls = *max_element(cls, cls + N);int max_num = *max_element(nums, nums + N);// hash二維數(shù)組計(jì)數(shù)int hashTable[max_cls + 1][max_num + 1];// 全０初始化memset(hashTable, 0, sizeof(hashTable));for (int i = 0; i < N; i++)hashTable[cls[i]][nums[i]]++;//類排序去重vector<int> v2;sort(cls, cls+N);unique_copy(cls, cls + N, back_inserter(v2));//nums排序去重vector<int> v;sort(nums, nums + N);unique_copy(nums, nums + N, back_inserter(v));for (int i = 0; i < v2.size(); i++) {cout << v2[i] << "={";for (int j = 0; j < v.size(); j++) {cout << v[j] << '=' << hashTable[v2[i]][v[j]];if (j < v.size() - 1) cout << ',';}cout << '}' << endl;}}}return 0; }轉(zhuǎn)載于:https://www.cnblogs.com/lingr7/p/9536396.html
總結(jié)
以上是生活随笔為你收集整理的问题 B: 分组统计的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： UVA 294 - Divisors （
- 下一篇： JavaScript之图片操作3