我正在尝试解决以下难题：
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所有数字之间的运算，结果将是隐身号码。
所以我想扩展这个想法来解决这个难题。我所需要的只是一个类似异或的函数（或运算符），它在第三次应用时会产生 0：
SEED xor3 X xor3 X xor3 X = SEED
X xor3 Y xor3 SEED xor3 X xor3 Y xor3 Y xor3 X = SEED
对于这样的功能有什么想法吗？
将 XOR 视为对以二进制（即基数 2）表示的数字的每一位求和，模 2。
现在考虑一个由以下组成的数值系统tribits0、1、2。也就是说，它的基数是3。
运营商T现在变成对任何数字的运算，分解为这个基数。与 XOR 一样，您将位相加，但不同之处在于运算符T以模 3 运行。
你可以很容易地证明a T a T a对于任何一个都为零a。您还可以证明T既可交换又可结合。这是必要的，因为一般来说，您的序列会将数字弄乱。
现在将其应用到您的号码列表中。操作结束时，输出将是b where b = o T o and o是恰好出现两次的数字。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
