现在有一个数组,数组里除了一个数出现了1次,其他数字都出现了3次,想找到这个只出现1次的数字。
然后我的想法是用有限状态机进行建模,因为每个数都可以用32位二进制数来表示,那么将数组中所有数的每一个二进制位累加,那么最后每个位对3取余一定是0或者1,因为出现3次的都抵消了。接着用00,01,10分别表示每次计算,余数位0,余数为1和余数为2的状态,这是状态转换图:
想知道只出现一次的那个数,应该用什么表示呢,然后状态转换里没有11这个状态有没有问题
现在有一个数组,数组里除了一个数出现了1次,其他数字都出现了3次,想找到这个只出现1次的数字。
然后我的想法是用有限状态机进行建模,因为每个数都可以用32位二进制数来表示,那么将数组中所有数的每一个二进制位累加,那么最后每个位对3取余一定是0或者1,因为出现3次的都抵消了。接着用00,01,10分别表示每次计算,余数位0,余数为1和余数为2的状态,这是状态转换图:
想知道只出现一次的那个数,应该用什么表示呢,然后状态转换里没有11这个状态有没有问题
如果你要照这种思路解题
那么假设数组长度为n
1.如何表示这个数:用32个状态机在时刻n后的结果依次排列就是你要找的数。因为每一位都是一个独立的状态机,与其他位毫无关系。
2.其次没有11这个状态无所谓。
3.你应该把原题发上来,或者描述清楚一些