解题思路:
标准思路,每一次输入的时候对前所有数据进行检查,出现相似后立即计数,为全体同样出现的数字进行自增加一。
参考代码:
#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语言代码)浏览:542 |
数组输出 (C语言代码)错误???浏览:567 |
WU-拆分位数 (C++代码)浏览:788 |
C语言程序设计教程(第三版)课后习题10.4 (C语言代码)浏览:550 |
分糖果 (C语言代码)浏览:920 |
C语言程序设计教程(第三版)课后习题5.7 (C语言代码)浏览:785 |
C语言程序设计教程(第三版)课后习题11.3 (C语言代码)浏览:2166 |
剔除相关数 (C语言代码)浏览:1092 |
C语言程序设计教程(第三版)课后习题1.6 (C语言代码)浏览:631 |
2003年秋浙江省计算机等级考试二级C 编程题(1) (C语言代码)浏览:1326 |