该题如下描述:
有101个数,为[1,100]之间的数,其中一个数是重复的,如何寻找这个重复的数,其时间复杂度和空间复杂度是多少?
本人在读了这道题后,顿感惊讶……不可能这么简单哦!难道我哪里想错了?
困惑之下写出我自己想法,希望各位朋友一起讨论一下。如果各位发现我哪里想错了,请指出一下,感谢!
解决思路:
1)如果题中的“数”指整数,那这道题,我觉得太简单了。
直接把这101 个数相加求出累计和S1;再求出1+2+3+...+100的和S2,然后直接S1-S2就能得出这个重复数是多少。
时间复杂度应该是n,空间复杂度应该是1
2)如果题中的“数”指实数,那也比较简单。
A思路:直接来个二重循环,就能找出来了。如此的话,时间复杂度:n的二次方,空间复杂度:1
B思路:先排序,再来个一重循环。排序如果用快速或归并之类的,则整个时间复杂度为n(logn),空间复杂度为:n
正确答案如何,我就不敢确定了。