求助leetcode的一道题

[b]Single Number II Total Accepted: 12874 Total Submissions: 39608

My Submissions

Given an array of integers, every element appears three times except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?[/b]下面是一种解法：

• ones as a bitmask to represent the ith bit had appeared once.
• twos as a bitmask to represent the ith bit had appeared twice.
• threes as a bitmask to represent the ith bit had appeared three times.
  

int singleNumber(int A[], int n) {   
       int ones = 0, twos = 0, threes = 0;   
       for (int i = 0; i < n; i++)
     {        
         twos |= ones & A;        
         ones ^= A[i];        [/i]
[i]         threes = ones & twos;        [/i]
[i]         ones &= ~threes;        [/i]
[i]         twos &= ~threes;    [/i]
[i]     }    [/i]
[i]      return ones;[/i]
[i]}



哪位高手能解释一下 上面的代码是什么意思？
[/i]

I don't understand this neither. What does |= means?

KikSamuel 发表于 2014-4-21 10:26
I don't understand this neither. What does |= means?

按位或。。。。。

sum all the numbers only at a certain bit and mod 3, then you can get the corrsponding bit of the single number~~~

可以用一个数组来表示各个位上的1的个数然后mod 3，不过这种方法不是最好，最好的就是那种方法了，不过不是很容易理解

你可以多看几个类似这种的解法 就知道门路了 一开始很难想的

正好做了这道题，也看了你说的Quora上那个人给的解法。其实只要用one和two就够了，我把每条代码注释一下也许能帮助你理解吧：

class Solution:
    # @param A, a list of integer
    # @return an integer
    def singleNumber(self, A):
        #把数字想象成3进制的，2+1就进位成0 one和two分别记录了所有1和2的位置
        one=0   #存储了目前为止所有1的位置
        two=0   #存储了目前为止所有2的位置
        for a in A:
            tmp=one  #临时保存修改前的one
            one=(~(one|two)&a)|(~a&one)   #两部分：左边是表示处理a之前所有0和a中所有1结合成为1   右边是表示处理a之前所有0（即one）和a中所有1结合成为1 最后左右或一下就是新的所有1的位置
            two=(two&~a)|(tmp&a)   #两部分： 左边是表示处理a之前所有2和a中所有0结合成为2   右边是表示处理a之前所有1和a中所有1结合成为2 最后左右或一下就是新的所有2的位置   其他的1+2，0+0都成为了0
        return one #最后所有1的位置组成的数就是那个只出现1次的数字，因为其他数字1都加了3次变成了0

leoyang 发表于 2014-4-25 10:46
正好做了这道题，也看了你说的Quora上那个人给的解法。其实只要用one和two就够了，我把每条代码注释一下也许 ...

mark...非常感谢...

leoyang 发表于 2014-4-25 10:46
正好做了这道题，也看了你说的Quora上那个人给的解法。其实只要用one和two就够了，我把每条代码注释一下也许 ...

为什么要用~？

blactangeri 发表于 2014-4-25 11:55
为什么要用~？

~是取反
解释一下这条~(one|two)&a
one|two的到的结果是所有不是0的位都变成1，那取反之后所有时0的位就都变成1了，再和a与一下得出的结果为1的那些位就都是0+1的结果了。