137. Single Number II.md

137. Single Number II

Problem

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

tag:

• 位运算

Solution

方法一： 统计所有数的每一位之和，对3取余，即为出现一次的

java

    public int singleNumber(int[] nums) {
        int[] c =  new int[32];
        int res = 0;
        for(int i=0; i<32; i++) {
            for(int n : nums) {
                c[i] += (n>>i)&1;
            }
            res |= ((c[i]%3)<<i);
        }
        return res;
    }

go

方法二

cann't understand :(

    public int singleNumber(int[] nums) {
        //we need to implement a tree-time counter(base 3) that if a bit appears three time ,it will be zero.
        //#curent  income  ouput
        //# ab      c/c       ab/ab
        //# 00      1/0       01/00
        //# 01      1/0       10/01
        //# 10      1/0       00/10
        // a=~abc+a~b~c;
        // b=~a~bc+~ab~c;
        int a=0;
        int b=0;
        for(int c:nums){
            int ta=(~a&b&c)|(a&~b&~c);
            b=(~a&~b&c)|(~a&b&~c);
            a=ta;
        }
        //we need find the number that is 01,10 => 1, 00 => 0.
        return a|b;

    }