在阅读了这个有趣的问题之后,我想起了曾经有过一次我从未满意地回答的棘手面试问题:
给出一个n个32位无符号整数的数组,其中每个元素(除了一个)重复三次.在O(n)时间内并使用尽可能少的辅助空间,找到不出现三次的数组的元素元素.
举个例子,给定这个数组:
1 1 2 2 2 3 3 3 3 3 3
给定数组时,我们输出1
3 2 1 3 2 1 2 3 1 4 4 4 4
我们输出4.
这可以通过使用哈希表计算每个元素的频率在O(n)时间和O(n)空间中轻松解决,但我强烈怀疑,因为问题语句特别提到数组包含32位无符号整数有一个更好的解决方案(我猜O(1)空间).
有没有人对如何解决这个问题有任何想法？