谈谈百度一面中的某道题

该题如下描述：

　有101个数，为[1，100]之间的数，其中一个数是重复的，如何寻找这个重复的数，其时间复杂度和空间复杂度是多少？

　　本人在读了这道题后，顿感惊讶……不可能这么简单哦！难道我哪里想错了？

困惑之下写出我自己想法，希望各位朋友一起讨论一下。如果各位发现我哪里想错了，请指出一下，感谢！

解决思路：

　　1)如果题中的“数”指整数，那这道题，我觉得太简单了。

　　　　直接把这101 个数相加求出累计和S1;再求出1+2+3+...+100的和S2,然后直接S1-S2就能得出这个重复数是多少。

　　　　时间复杂度应该是n,空间复杂度应该是1

      2)如果题中的“数”指实数，那也比较简单。

　　　Ａ思路：直接来个二重循环，就能找出来了。如此的话，时间复杂度：n的二次方，空间复杂度:1

            B思路：先排序，再来个一重循环。排序如果用快速或归并之类的，则整个时间复杂度为n(logn),空间复杂度为：n

正确答案如何，我就不敢确定了。