这是一个面试问题.
我得到了一系列n+1来自该范围的整数[1,n].数组的属性是它有k (k>=1)重复,每个副本可以出现两次以上.任务是找到在尽可能最佳的时间和空间复杂度下不止一次出现的数组元素.
在经历了重大的挣扎之后,我自豪地想出了O(nlogn)一个占据O(1)空间的解决方案.我的想法是将范围[1,n-1]分成两半,并确定两半中的哪一半包含来自输入数组的更多元素(我使用的是Pigeonhole原理).该算法递归地继续,直到它达到发生两次的间隔[X,X],X这是重复的.
面试官很满意,但后来他告诉我存在O(n)恒定空间的解决方案.他慷慨地提供了一些提示(与排列相关的东西？),但我不知道如何提出这样的解决方案.假设他没有说谎,有人可以提供指导吗？我搜索了SO,发现这个问题很少(更容易)变化,但不是这个特定的.谢谢.
编辑:为了使事情变得更复杂,采访者提到不应该修改输入数组.