快速找到该数字，如何建立解空间？？？

比如：
1, 8, 2, 1, 2, 3, ........, 1, 1, 2, 3, 7, 4, 3, ........., 8, 5, 2
^  ^  ^  ^  ^  ^  ^      ^  ^  ^  ^  ^  ^  ^  ^  ^       ^  ^  ^  ^
1  2  3  4  5  6  7      5  5  5  5  5  5  5  5  5       9  9  9  1
                         0  0  0  0  0  0  0  0  0       9  9  9  0
                         0  0  0  0  0  0  0  0  0       9  9  9  0
                         0  0  0  0  0  0  0  0  0       9  9  9  0
                         0  0  0  0  0  0  0  0  0       9  9  9  0
                         0  1  2  3  4  5  6  7  8       7  8  9  0
                                                                  0

可以看到在500001和500002处有两个1重复了，但其它位置数字之间都是没有重复的，应该就是这个意思。

[ 本帖最后由 lz1091914999 于 2011-8-17 19:56 编辑 ]

都100万个（1～9）的数字了 怎么才1个数字重复两次啊 求解

回复2楼 只有1个数字重复两次没有问题。其它数字可以多于两次嘛。

回复楼主 这道题只需统计每个数字出现的次数就可以了，算法复杂度为O(N)。不可能有更快的算法。

也就是说除了迭代也没有其它算法了？

- - 没想法了 - -

[ 本帖最后由 草狼 于 2011-8-17 20:04 编辑 ]

0(N)是什么意思？

不懂，

不好意思，之前没看例子，还是理解错了。楼主说的应该是出现的连续次数是两次。而之前我的理解是在100万个数字里只出现两次人。

这样就不是做统计，而是顺序扫描。在保证输入数据的正确性的情况下，可以扫描到连续出现两次的数字时停止。不过算法的时间复杂度不变。

O是时间复杂度的定义函数符号。中间的表达式是计算规模对应计算时间的函数，通常是个多项式，而且略去低次项，仅保留高次项。对于计算时间不随计算规模变化的算法认为它的时间复杂复是O(1)。 平时的讨论中人们也经常符号O，而说一个算法的时间复杂度是N^2, N, logN, N*logN, 1等等。
当一个算法的时间复杂度为N时，表示算法所用的时间随着计算规模的增加而线性增加。以你这个题目为例，如果100万个数字需要花10秒的时间，那么计算200万个数字就花20秒。
如果换一个复杂度为N^2的算法的话，计算200万个数字需要40秒的时间。
显然算法复杂度的阶数越低在大规模计算时用的时间越少。这是衡量算法好坏的最重要的指标。
与之相应还有个空间复杂度。不过随着现在计算机内存越来越大，这个指标已经不是那么重要了。当然，同样的速度下，还是占用内存越小越好。

可以用排除法。用switch

谢谢啊，基本上理解了，不过我没上过高中啊，还记得我向你索要数学书吗？