解题思路:
标准思路,每一次输入的时候对前所有数据进行检查,出现相似后立即计数,为全体同样出现的数字进行自增加一。
参考代码:
#include<bits/stdc++.h> #define hh ios::sync_with_stdio(false),cin.tie(0),cout.tie(0); #pragma GCC optimize(2) using namespace std; const int maxn=20005; int a[maxn],b[maxn]; int main() { hh; int n,m; while(cin>>n>>m) { memset(a,0,sizeof(a)); memset(b,0,sizeof(b)); //用以清空两数组,因为多组数据嘛。 for(int i=0; i<n; i++) { cin>>a[i]; b[i]=0; //从零开始的数组生活..(雾) for(int j=0; j<i; j++) { bool flag=false; if(a[j]==a[i]) { b[j]++; flag=true; } if(flag) { b[i]++; //这里主要是用于自身也需要增加1 } } } for(int i=0; i<n; i++) { if(b[i]==0) { cout<<"BeiJu"<<endl; } else { cout<<b[i]<<endl; } } } return 0; } //AC
这样的方法比较容易想到,也是我第一个提交的方法,不难发现,这份代码,面对众多数据的时候,其时间复杂度是近似于o(n^2)的,但其后可以发现,可以利用Hash(哈希)表的方式来减少时间复杂度,达到优化的目的,众所周知,哈希表的重点就是为了建立哈希函数,达到地址与目标的对应,经过思考后发现,第几本书的喜好人数是与每个人喜好有关的,于是可以建立相关的哈希函数(省略),具体思路可以看代码:
#include<bits/stdc++.h> #pragma GCC optimize(2) using namespace std; const int maxn=20005; int main() { int n, m, P; int r[maxn]; //读者的喜好 while (cin >> n >> m) { int b[maxn] = {0}; //书的编号 for (int i=0; i<n; ++i) { cin >> P; r[i] = P; b[P]++; } for (int i=0; i<n; ++i) { int anyFriend = b[r[i]] - 1; //Hash关系 if (anyFriend != 0) cout << anyFriend << endl; else cout << "BeiJu" << endl; } } return 0; } //AC
时间复杂度瞬间减下来了,如果需要多组搜索式输出的话,这样的方法更加能够体现出优越性。
0.0分
3 人评分
C语言程序设计教程(第三版)课后习题3.7 (C++代码)浏览:998 |
C语言程序设计教程(第三版)课后习题1.5 (C语言代码)浏览:559 |
C语言训练-大、小写问题 (C语言代码)浏览:2357 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:617 |
C语言程序设计教程(第三版)课后习题6.5 (C++代码)浏览:458 |
C语言训练-数字母 (C语言代码)浏览:608 |
1012题解浏览:871 |
C语言程序设计教程(第三版)课后习题10.2 (C语言代码)浏览:1466 |
C二级辅导-阶乘数列 (C语言代码)浏览:522 |
字符串的输入输出处理 (C语言代码)浏览:1017 |