找到第一个独特元素

Question

我在采访中遇到了这个问题,我无法回答.您必须在数组中找到第一个唯一元素(整数).例如:

3,2,1,4,4,5,6,6,7,3,2,3

然后,独特的元素是1, 5, 7第一个独特的1.

解决方案要求:

O(n)时间复杂度.

O(1)空间复杂性.

我试着说:

使用Hashmaps,Bitvector ......但它们都没有空间复杂度O(1).

谁能告诉我空间O(1)的解决方案？

Answer 1

这是一个不可能的非严格证明:众所周知,当您使用O(1)空间时,重复检测不能比O(n*log n)更好.假设当前问题在O(n)时间和O(1)存储器中是可解的.如果我们得到第一个非重复数的索引'k'为0以外的任何值,我们知道k-1是重复的,因此再一次扫描数组我们可以得到它的重复,使重复检测为O( n)运动.

同样,它并不严谨,我们可以进入最坏情况分析,其中k总是为0.但它可以帮助您思考并说服面试官不太可能.

http://en.wikipedia.org/wiki/Element_distinctness_problem说:在大小为n的多集中出现超过n/k次的元素可以在时间O(n log k)中找到.这里k = n,因为我们想要多次出现的元素.