本文共 1029 字,大约阅读时间需要 3 分钟。
原题:
大意是有个最多100W长度的整数数组,里面只有2个数相同,我们的任务是输入这组数,输出相同的那个数.
最容易想到的方法显然是遍历数组的每个数,进行对比,碰到相同的,则输出,这时该算法的时间复杂度大概是n^2,然而题目的时间限制是1s,考虑到数组可以是100W长度,这样显然会超时,我试着提交了下,果然提示TLE..
接着对代码进行优化,《编程珠玑》一书第一章说的就是位图数据结构的妙用,果然该方法对处理大量数据问题效果拔群。此时时间复杂度仅约为n。以下是我的代码:
#include#include #define N 1000010char a[N];int main(void){ int n; int i; int j; while(scanf("%d", &n) != EOF) { memset(a, 0, n); for(i = 0; i < n; i++) { scanf("%d", &j); if(a[j] == 0) { a[j] = 1; } else { printf("%d\n", j); } } } return 0;}
该算法的缺点显而易见,由于使用了位图,需要将数组初始化为0值,于是用到了memset()函数,这从另一方面加大了程序的耗时,然而这样的耗时对于整体的拖累不是很明显,相比于使用遍历法,甚至可以忽略不计了。
该方法确实算不上最优解,只是记录了下我的思考过程,看了下该题的状态,第一名的大牛用时显然比我低得多。路漫漫其修远兮。。。。
转载地址:http://rysoi.baihongyu.com/