一道腾讯算法题引出的思考

已经完成了腾讯实习生二面了,忐忑的心终于安定了一些。这次面试感觉发挥得不是很好,一个点是自己笔试的基础题做得比较差,还是很有必要针对校招做一些基础知识的积累和准备了,二是有一道算法题答得不理想,两次请教面试官,都被面试官婉拒了,哎,天资愚钝,现在还没想出时间复杂度能小于O(n)的解法。题目大概是这样的

目前有一万零一个数(无序),范围是1~10000, 除了有两个重复数字之外,其它数字都不重复,怎么最快找出这两个重复数字?

这个题很直观的一个解法就是遍历整个数组,然后把遍历过的数方法一个set中,每次遍历遇到新数字的时候,再判断它是否在该set中即可,代码大概如下

def find_repeatable_num(arr):
    nums = set()
    for i in arr:
        if i in nums:
            return i
        nums.add(i)

由于set查找的时间复杂度近似为O(1),因此这种方法时间复杂度为O(N),空间复杂度为O(N)。面试官说还有更优的方法

当时本来是按这个思路写的,但是也怪自己没和面试官进行沟通,看他到底是否关注空间复杂度。然后自作主张对数组进行了排序,把空间复杂度变成了O(1),然后排序的代价为O(nlogn),所以整体时间复杂度变成了O(nlogn)了。

回来的时候一直在思考这个问题,后来想出了一种时间复杂度还是O(N),空间复杂度为O(1)的方法: 这种方法主要使用高中数学知识(感谢自己的数学老师,高中数学成绩还算比较优异)。由于1~10000这个连续的等差数列,我们可以很容易求出它的整体和

n*(n+1)/2  # 这里我们求1~10000的和即可

然后我们再求出这个一万零一个数的和,两者相减就是结果了。这种方法算是利用到了题目中的特性:1~10000连续的数字,且只有一个重复数字

这种方法时间复杂度为O(N),空间复杂度为O(1),它的主要消耗是求数组和。常数项的操作也很少,这也是我自己能想到的最好的解法了。

刚才小伙伴发了一个链接给我,这个题目在剑指offer上也有涉及,它主要的思路是将每个位置的值拿来和下标做比较,如果第一次遇到的下标和值不相等的情况,那么就把该值放到和值相等的下标的那个位置,这样子一个怼一个,找出重复的情况。但是这个方法在最坏情况下时间复杂度还是O(N),空间复杂度倒是O(1)

所以究竟是面试官想要时间复杂度小于O(N)的解法,还是我误解了他的意思,他想要的是O(N)时间复杂度,额外空间复杂度O(1)的解法?如果是前者的话,我确实找不到更好的办法了。如果是后者的话,那说明我自己的沟通能力和主动性还应该再加强。真想请教一下面试官这个问题怎么能让时间复杂度更小,可惜没面试官的联系方式。