问题描述
我正在尝试解决以下难题:
I'm trying to solve the following puzzle:
Given a stream of numbers (only 1 iteration over them is allowed) in which all numbers appear 3 times, but 1 number appear only 2 times, find this number, using O(1) memory.
我首先想到的是,如果所有数字出现2次,而只有1个数字出现一次,则可以在所有数字之间使用xor
运算,结果将是隐身数字.
I started with the idea that, if all numbers appeared 2 times, and 1 number only once, I could use xor
operation between all numbers and the result would be the incognito number.
所以我想扩展这个想法来解决这个难题.我需要的只是一个类似xor的函数(或运算符),在第三个apply上将产生0:
So I want to extend this idea to solve the puzzle. All I need is a xor-like function (or operator), which would yield 0 on the third apply:
SEED xor3 X xor3 X xor3 X = SEED
X xor3 Y xor3 SEED xor3 X xor3 Y xor3 Y xor3 X = SEED
对这种功能有什么想法吗?
Any ideas for such a function?
推荐答案
将XOR视为二进制模(以2为基数)表示的数字的每一位的总和.
Regard XOR as summation on each bit of a number expressed in binary (i.e. a radix of 2), modulo 2.
现在考虑由 tribits 0、1和2组成的数值系统.也就是说,它的基数为3.
Now consider a numerical system consisting of tribits 0, 1, and 2. That is, it has a radix of 3.
运算符T
现在可以分解为该基数,并且可以对任何数字进行运算.与在XOR中一样,您需要对位求和,但不同之处在于运算符T
以模3形式运行.
The operator T
now becomes an operation on any number, decomposed into this radix. As in XOR, you sum the bits, but the difference is that operator T
is ran in modulo 3.
对于任何a
,您可以轻松地显示a T a T a
为零.您还可以显示T
既可交换又可关联.这是必要的,因为通常情况下,您的序列将使数字混乱.
You can easily show that a T a T a
is zero for any a
. You can also show that T
is both commutative and associative. That is necessary since, in general, your sequence will have the numbers jumbled up.
现在将其应用于您的号码列表.操作结束时,输出将为b
,其中b = o T o
和o
是恰好出现两次的数字.
Now apply this to your list of numbers. At the end of the operation, the output will be b
where b = o T o
and o
is the number that occurs exactly twice.
这篇关于三向异或功能的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!