Single Number II的位操作解法

2019-04-14 19:53发布

站内文章 / 模拟电子
15341 0 1669
看了很多篇这个问题的位操作解法，感觉都是一句带过，自己模拟了下才真正明白。 leetcode原题，大意就是一个数组只有一个数出现了一次，其他数都出现3次，设计算法找出这个出现一次的数。
 位操作解法如下，时间复杂度O(n)。 int singleNumber(int A[], int n) { int ones=0; int twos=0; int threes=0; for(int i=0;i

其中ones表示将数组中所有整形数转为二进制后，每个位上，1出现次数为1次的情况，如循环到某一步时，ones=00001001，即5时，表示前面的数中，第一位出现1的有个1个，第四位出现1的有一个。同理，twos表示某一位上出现1个次数为2。 这样，就比较好理解当ones和twos中的某一位同时为1时表示二进制1出现3次，此时需要清零。即用二进制模拟三进制计算，从而，当ones和twos某一位均为1时，threes对应的位置 置1，然后取反，和ones、twos、对应进行&操作，将其清零。最后，得到的ones就是出现一次的数

热门文章