Tag Archives: 算法

寻找只出现了2次的数字

在一个存放着数字的数组里,有一个数字出现了2次,其余的都出现了3次,如何找到那个出现了2次的数字?

这是在知乎上看到的一个很有趣的问题。 看到这题我立刻就想到了另一个经典的问题,即在一堆数据里,有一个数字出现了奇数次,其他数据都出现了偶数次,如何找到那个出现了奇数次的数据?一个正常 人的第一反应九成九是哈希,但是事实上这个问题存在一个非常简单、而且时间复杂度非常低的方法,即把所有的数据异或起来,最后的结果就是我们要找的数据。

这个方法乍看也许很玄妙,但其实原理很简单,即两个相同的数异或的结果是0。把所有的数据异或起来,出现了偶数次的数据都在自己和自己异或的过程中湮灭了,于是最后只剩下那个出现了奇数次的数据站在那儿茕茕孑立。

但是如果某个数组里只有一个数出现了为偶数的2次,其余的都出现了为奇数的3次应该怎么办?我一开始囿于成见想了很久怎么用异或来做这件事情,最终 结果是恍然悟出我在做一件多么愚蠢的事情——异或的结果只能让我们想要找的那个数变得如羚羊挂角,无迹可求。想要不借助于哈希这种无聊的办法而得到这题的 答案,必须要使用一种运算让一个数一但出现了3次,就会自我抵消掉。

下面的这个办法不是我想出来的,而是知乎上的一位牛人所给出的。即把所有的数据当作一个3进制数,然后在每一位上,把所有的数据这一位的3进制数加起来,乘以2再对3取模,最后得到的3进制数的值(也就是对应的10进制数)就是我们需要的答案。

这个巧妙算法的原理同样也很简单。一个数字如果出现了3次,那么把3个它加起来一定是3的倍数,即对3取模为0。但是如果一股脑把所有数据加起来再 对3取模,我们只能得到0,1,2三种值,明显离我们的答案存在的可能性相差甚远。所以这个方法又采取了另一个巧妙的思想即把所有数据看作3进制数,然后 在每一位上利用这个原理来处理。这和之前我们提到的那个题目用二进制运算异或有异曲同工之妙。

下面是我用ruby写的一种该算法的实现,具体的实现细节可能和原算法所描述的稍有不同,但主要思想是一致的。

事实上在这个问题上我们还能更进一步地思考,如果一陀数据里只有一个数出现了偶数次,其余的数都出现了奇数次,如何找到那个出现了偶数次的数据?欢迎各位在这里给出你思考的答案。