Massive Algorithms: LeetCode 137

https://leetcode.com/problems/single-number-ii

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

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

https://discuss.leetcode.com/topic/2926/accepted-code-with-proper-explaination-does-anyone-have-a-better-idea

The code makes use of 2 variables.

ones - At any point of time, this variable holds XOR of all the elements which have
appeared "only" once.
twos - At any point of time, this variable holds XOR of all the elements which have
appeared "only" twice.

So if at any point time,

A new number appears - It gets XOR'd to the variable "ones".
A number gets repeated(appears twice) - It is removed from "ones" and XOR'd to the
variable "twos".
A number appears for the third time - It gets removed from both "ones" and "twos".

The final answer we want is the value present in "ones" - coz, it holds the unique element.

So if we explain how steps 1 to 3 happens in the code, we are done.
Before explaining above 3 steps, lets look at last three lines of the code,

common_bit_mask = ~(ones & twos)

ones & = common_bit_mask

twos & = common_bit_mask

All it does is, common 1's between "ones" and "twos" are converted to zero.

For simplicity, in all the below explanations - consider we have got only 4 elements in the array (one unique element and 3 repeated elements - in any order).

Explanation for step 1

Lets say a new element(x) appears.

CURRENT SITUATION - Both variables - "ones" and "twos" has not recorded "x".

Observe the statement "twos| = ones & x".
Since bit representation of "x" is not present in "ones", AND condition yields nothing. So "twos" does not get bit representation of "x".
But, in next step "ones ^= x" - "ones" ends up adding bits of "x". Thus new element gets recorded in "ones" but not in "twos".

The last 3 lines of code as explained already, converts common 1's b/w "ones" and "twos" to zeros.
Since as of now, only "ones" has "x" and not "twos" - last 3 lines does nothing.

Explanation for step 2.

Lets say an element(x) appears twice.

CURRENT SITUATION - "ones" has recorded "x" but not "twos".

Now due to the statement, "twos| = ones & x" - "twos" ends up getting bits of x.
But due to the statement, "ones ^ = x" - "ones" removes "x" from its binary representation.

Again, last 3 lines of code does nothing.
So ultimately, "twos" ends up getting bits of "x" and "ones" ends up losing bits of "x".

Explanation for step 3.

Lets say an element(x) appears for the third time.

CURRENT SITUATION - "ones" does not have bit representation of "x" but "twos" has.

Though "ones & x" does not yield nothing .. "twos" by itself has bit representation of "x". So after this statement, "two" has bit representation of "x".
Due to "ones^=x", after this step, "one" also ends up getting bit representation of "x".

Now last 3 lines of code removes common 1's of "ones" and "twos" - which is the bit representation of "x".
Thus both "ones" and "twos" ends up losing bit representation of "x".

        int singleNumber(int A[], int n) {
            int ones=0, twos =0;
            int common_bit_mask;
            for(int i=0; i<n;i++)
            {
                 /* The expression "one & arr[i]" gives the bits that are
               there in both 'ones' and new element from arr[].  We
               add these bits to 'twos' using bitwise OR
     
               Value of 'twos' will be set as 0, 3, 3 and 1 after 1st,
               2nd, 3rd and 4th iterations respectively */
               
                twos= twos|(ones&A[i]);
                /* XOR the new bits with previous 'ones' to get all bits
               appearing odd number of times
     
               Value of 'ones' will be set as 3, 0, 2 and 3 after 1st,
               2nd, 3rd and 4th iterations respectively */
                ones=ones^A[i];
                 /* The common bits are those bits which appear third time
               So these bits should not be there in both 'ones' and 'twos'.
               common_bit_mask contains all these bits as 0, so that the bits can 
               be removed from 'ones' and 'twos'   
     
               Value of 'common_bit_mask' will be set as 00, 00, 01 and 10
               after 1st, 2nd, 3rd and 4th iterations respectively */
                common_bit_mask= ~(ones&twos); // handle when x happens three times
                /* Remove common bits (the bits that appear third time) from 'ones'
                 
               Value of 'ones' will be set as 3, 0, 0 and 2 after 1st,
               2nd, 3rd and 4th iterations respectively */
                ones &=common_bit_mask;
                /* Remove common bits (the bits that appear third time) from 'twos'
     
               Value of 'twos' will be set as 0, 3, 1 and 0 after 1st,
               2nd, 3rd and 4th itearations respectively */
                twos &=common_bit_mask;
            }
            return ones;
        }

https://discuss.leetcode.com/topic/34725/my-own-explanation-of-bit-manipulation-method-might-be-easier-to-understand

Consider the following fact:

Write all numbers in binary form, then for any bit 1 that appeared 3*n times (n is an integer), the bit can only present in numbers that appeared 3 times

e.g. 0010 0010 0010 1011 1011 1011 1000 (assuming 4-bit integers)
2(0010) and 11(1011) appeared 3 times, and digit counts are:

Digits 3 2 1 0

Counts 4 0 6 3

Counts%3 1 0 0 0

Counts on 2,1,0 are all times of 3, the only digit index that has Counts % 3 != 0 is 3

Therefore, to find the number that appeared only 1 or 2 times, we only need to extract all bits that has Counts %3 != 0

Now consider how we could do this by bit manipulation

since counts % 3 has only 3 states: 0(00),1(01),2(10)
we could use a TWO BIT COUNTER (Two, One) to represent Counts % 3, now we could do a little research on state transitions, for each bit, let B be the input bit, we can enumerate the all possible state transitions, Two+, One+ is the new state of Two, One. (here we need to use some knowledge in Digital Logic Design)

Two One B Two+ One+

0 0 0 0 0

0 0 1 0 1

0 1 0 0 1

0 1 1 1 0

1 0 0 1 0

1 0 1 0 0

1 1 0 X X (X represents we don't care)

1 1 1 X X

We could then draw the Karnaugh map to analyze the logic (https://en.wikipedia.org/wiki/Karnaugh_map), and then we get:

One+ = (One ^ B) & (~Two)

Two+ = (~One+) & (Two ^ B)

Now for int_32, we need only 2 int_32 two represent Two and One for each bit and update Two and One using the rules derived above

    int singleNumber(vector<int>& nums) {
        int counterOne = 0;
        int counterTwo = 0;
        
        for (int i = 0; i < nums.size(); i++){
            counterOne = (~counterTwo) & (counterOne ^ nums[i]);
            counterTwo = (~counterOne) & (counterTwo ^ nums[i]);
        }
        return counterOne;
    }

https://discuss.leetcode.com/topic/11877/detailed-explanation-and-generalization-of-the-bitwise-operation-method-for-single-numbers

Statement of our problem: "Given an array of integers, every element appears k (k > 1) times except for one, which appears ptimes (p >= 1, p % k != 0). Find that single one."

As others pointed out, in order to apply the bitwise operations, we should rethink how integers are represented in computers -- by bits. To start, let's consider only one bit for now. Suppose we have an array of 1-bit numbers (which can only be 0 or 1), we'd like to count the number of 1's in the array such that whenever the counted number of 1 reaches a certain value, say k, the count returns to zero and starts over (In case you are curious, this k will be the same as the one in the problem statement above). To keep track of how many 1's we have encountered so far, we need a counter. Suppose the counter has m bits in binary form: xm, ..., x1 (from most significant bit to least significant bit). We can conclude at least the following four properties of the counter:

There is an initial state of the counter, which for simplicity is zero;
For each input from the array, if we hit a 0, the counter should remain unchanged;
For each input from the array, if we hit a 1, the counter should increase by one;
In order to cover k counts, we require 2^m >= k, which implies m >= logk.

Here is the key part: how each bit in the counter (x1 to xm) changes as we are scanning the array. Note we are prompted to use bitwise operations. In order to satisfy the second property, recall what bitwise operations will not change the operand if the other operand is 0? Yes, you got it: x = x | 0 and x = x ^ 0.

Okay, we have an expression now: x = x | i or x = x ^ i, where i is the scanned element from the array. Which one is better? We don't know yet. So, let's just do the actual counting:

At the beginning, all bits of the counter is initialized to zero, i.e., xm = 0, ..., x1 = 0. Since we are gonna choose bitwise operations that guarantee all bits of the counter remain unchanged if we hit 0's, the counter will be 0 until we hit the first 1 in the array. After we hit the first 1, we got: xm = 0, ...,x2 = 0, x1 = 1. Let's continue until we hit the second 1, after which we have: xm = 0, ..., x2 = 1, x1 = 0. Note that x1 changed from 1 to 0. For x1 = x1 | i, after the second count, x1 will still be 1. So it's clear we should use x1 = x1 ^ i. What about x2, ..., xm? The idea is to find the condition under which x2, ..., xm will change their values. Take x2 as an example. If we hit a 1 and need to change the value of x2, what must be the value of x1 right before we do the change? The answer is: x1 must be 1 otherwise we shouldn't change x2 because changing x1 from 0 to 1 will do the job. So x2 will change value only if x1 and i are both 1, or mathematically, x2 = x2 ^ (x1 & i). Similarly xm will change value only when xm-1, ..., x1 and i are all 1: xm = xm ^ (xm-1 & ... & x1 & i). Bingo, we've found the bitwise operations!

However, you may notice that the bitwise operations found above will count from 0 until 2^m - 1, instead of k. If k < 2^m - 1, we need some "cutting" mechanism to reinitialize the counter to 0 when the count reaches k. To this end, we apply bitwise AND to xm,..., x1 with some variable called mask, i.e., xm = xm & mask, ..., x1 = x1 & mask. If we can make sure that mask will be 0 only when the count reaches k and be 1 for all other count cases, then we are done. How do we achieve that? Try to think what distinguishes the case with k count from all other count cases. Yes, it's the count of 1's! For each count, we have unique values for each bit of the counter, which can be regarded as its state. If we write k in its binary form: km,..., k1. we can construct mask as follows:

mask = ~(y1 & y2 & ... & ym), where yj = xj if kj = 1 and yj = ~xj if kj = 0 (j = 1 to m).

Let's do some examples:

k = 3: k1 = 1, k2 = 1, mask = ~(x1 & x2);

k = 5: k1 = 1, k2 = 0, k3 = 1, mask = ~(x1 & ~x2 & x3);

In summary, our algorithm will go like this:

for (int i : array) {
    xm ^= (xm-1 & ... & x1 & i);
    xm-1 ^= (xm-2 & ... & x1 & i);
    .....
    x1 ^= i;
    
    mask = ~(y1 & y2 & ... & ym)  where yj = xj  if kj = 1 and  yj = ~xj  if kj = 0 (j = 1 to m).

    xm &= mask;
    ......
    x1 &= mask;
}

Now it's time to generalize our results from 1-bit number case to 32-bit integers. One straightforward way would be creating 32counters for each bit in the integer. You've probably already seen this in other posted codes. But if we take advantage of bitwise operations, we may be able to manage all the 32 counters "collectively". By saying "collectively" we mean using m 32-bit integers instead of 32 m-bit counters, where m is the minimum integer that satisfies m >= logk. The reason is that bitwise operations apply only to each bit so operations on different bits are independent of each other(kind obvious, right?). This allows us to group the corresponding bits of the 32 counters into one 32-bit integer (for schematic steps, see comments below). Since each counter has mbits, we end up with m 32-bit integers. Therefore, in the algorithm developed above, we just need to regard x1 to xm as 32-bit integers instead of 1-bit numbers and we are done. Easy, hum?

The last thing is what value we should return, or equivalently which one of x1 to xm will equal the single element. To get the correct answer, we need to understand what the m 32-bit integers x1 to xm represent. Take x1 as an example. x1 has 32 bits and let's label them as r (r = 1 to 32). After we are done scanning the input array, the value for the r-th bit of x1 will be determined by the r-th bit of all the elements in the array (more specifically, suppose the total count of 1 for the r-th bit of all the elements in the array is q, q' = q % k and in its binary form: q'm,...,q'1, then by definition the r-th bit of x1 will be equal to q'1). Now you can ask yourself this question: what does it imply if the r-th bit of x1 is 1?

The answer is to find what can contribute to this 1. Will an element that appears k times contribute? No. Why? Because for an element to contribute, it has to satisfy at least two conditions at the same time: the r-th bit of this element is 1 and the number of appearance of this 1 is not an integer multiple of k. The first condition is trivial. The second comes from the fact that whenever the number of 1 hit is k, the counter will go back to zero, which means the corresponding bit in x1 will be reset to 0. For an element that appears k times, it's impossible to meet these two conditions simultaneously so it won't contribute. At last, only the single element which appears p (p % k != 0) times will contribute. If p > k, then the first k * [p/k] ([p/k]denotes the integer part of p/k) single elements won't contribute either. Then we can always set p' = p % k and say the single element appears effectively p'times.

Let's write p' in its binary form: p'm, ..., p'1. (note that p' < k, so it will fit into m bits). Here I claim the condition for x1 to equal the single element is p'1 = 1. Quick proof: if the r-th bit of x1 is 1, we can safely say the r-th bit of the single element is also 1. We are left to prove that if the r-th bit of x1 is 0, then the r-th bit of the single element can only be 0. Just suppose in this case the r-th bit of the single element is 1, let's see what will happen. At the end of the scan, this 1 will be counted p' times. If we write p' in its binary form: p'm, ..., p'1, then by definition the r-th bit of x1 will equal p'1, which is 1. This contradicts with the presumption that the r-th bit of x1 is 0. Since this is true for all bits in x1, we can conclude x1 will equal the single element if p'1 = 1. Similarly we can show xj will equal the single element if p'j = 1 (j = 1 to m). Now it's clear what we should return. Just express p' = p % k in its binary form and return any of the corresponding xj as long as p'j = 1.

In total, the algorithm will run in O(n * logk) time and O(logk) space.

Here is a list of few quick examples to show how the algorithm works:

k = 2, p = 1
k is 2, then m = 1, we need only one 32-bit integer(x1) as the counter. And 2^m = k so we do not even need a mask! A complete java program will look like:

    public int singleNumber(int[] A) {
         int x1 = 0;      
         for (int i : A) {
            x1 ^= i;
         }
         return x1;
    }

k = 3, p = 1
k is 3, then m = 2, we need two 32-bit integers(x2, x1) as the counter. And 2^m > k so we do need a mask. Write k in its binary form: k = '11', then k1 = 1, k2 = 1, so we have mask = ~(x1 & x2). A complete java program will look like:

    public int singleNumber(int[] A) {
         int x1 = 0;   
         int x2 = 0; 
         int mask = 0;
   
         for (int i : A) {
            x2 ^= x1 & i;
            x1 ^= i;
            mask = ~(x1 & x2);
            x2 &= mask;
            x1 &= mask;
         }

         return x1;  // p = 1, in binary form p = '01', then p1 = 1, so we should return x1; 
                     // if p = 2, in binary form p = '10', then p2 = 1, so we should return x2.
    }

k = 5, p = 3
k is 5, then m = 3, we need three 32-bit integers(x3, x2, x1) as the counter. And 2^m > k so we need a mask. Write k in its binary form: k = '101', then k1 = 1, k2 = 0, k3 = 1, so we have mask = ~(x1 & ~x2 & x3). A complete java program will look like:

    public int singleNumber(int[] A) {
         int x1 = 0;   
         int x2 = 0; 
         int x3  = 0;
         int mask = 0;
   
         for (int i : A) {
            x3 ^= x2 & x1 & i;
            x2 ^= x1 & i;
            x1 ^= i;
            mask = ~(x1 & ~x2 & x3);
            x3 &= mask;
            x2 &= mask;
            x1 &= mask;
         }

         return x1;  // p = 3, in binary form p = '011', then p1 = p2 = 1, 
                     // so we can return either x1 or x2; 
                     // But if p = 4, in binary form p = '100', then only p3 = 1, 
                     // which implies we can only return x3.
    }

You can easily come up with other examples

int singleNumber(int* nums, int numsSize, int k) //k>=2
{
    int counter[32];
    int i, j;
    int res = 0;
    
    for(i=0; i<32; i++)
        counter[i] = 0;
        
    for(i=0; i<numsSize; i++)
    {
        for(j=0; j<32; j++)
        {
            if(nums[i] & (1<<j))
                counter[j]++;
        }
    }
    
    for(i=0; i<32; i++)
    {
        if(counter[i]%k)
            res |= 1<<i;
    }
    
    return res;
}

It seems that this method is slower than some other methods when k==3. But I think that your method will be more universal and quicker when k is a big number.

https://discuss.leetcode.com/topic/2031/challenge-me-thx

First time number appear -> save it in "ones"

Second time -> clear "ones" but save it in "twos" for later check

Third time -> try to save in "ones" but value saved in "twos" clear it.

public int singleNumber(int[] A) {
    int ones = 0, twos = 0;
    for(int i = 0; i < A.length; i++){
        ones = (ones ^ A[i]) & ~twos;
        twos = (twos ^ A[i]) & ~ones;
    }
    return ones;
}

https://discuss.leetcode.com/topic/22821/an-general-way-to-handle-all-this-sort-of-questions

this kind of question the key idea is design a counter that record state. the problem can be every one occurs K times except one occurs M times. for this question, K =3 ,M = 1(or 2) .
so to represent 3 state, we need two bit. let say it is a and b, and c is the incoming bit.
then we can design a table to implement the state move.

current   incoming  next
a b            c    a b
0 0            0    0 0
0 1            0    0 1
1 0            0    1 0
0 0            1    0 1
0 1            1    1 0
1 0            1    0 0

like circuit design, we can find out what the next state will be with the incoming bit.( we only need find the ones)
then we have for a to be 1, we have

    current   incoming  next
    a b            c    a b
    1 0            0    1 0
    0 1            1    1 0

and this is can be represented by

a=a&~b&~c + ~a&b&c

and b can do the same we , and we find that

b= ~a&b&~c+~a&~b&c

and this is the final formula of a and b and just one of the result set, because for different state move table definition, we can generate different formulas, and this one is may not the most optimised. as you may see other's answer that have a much simple formula, and that formula also corresponding to specific state move table. (if you like ,you can reverse their formula to a state move table, just using the same way but reversely)

for this questions we need to find the except one
as the question don't say if the one appears one time or two time ,
so for ab both

01 10 => 1
00 => 0

we should return a|b;
this is the key idea , we can design any based counter and find the occurs any times except one .

    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;
        
    }

X. O(32n)

https://discuss.leetcode.com/topic/43166/java-o-n-easy-to-understand-solution-easily-extended-to-any-times-of-occurance

The usual bit manipulation code is bit hard to get and replicate. I like to think about the number in 32 bits and just count how many 1s are there in each bit, and sum %= 3 will clear it once it reaches 3. After running for all the numbers for each bit, if we have a 1, then that 1 belongs to the single number, we can simply move it back to its spot by doing ans |= sum << i;

This has complexity of O(32n), which is essentially O(n) and very easy to think and implement. Plus, you get a general solution for any times of occurrence. Say all the numbers have 5 times, just do sum %= 5.

move sum %= 3 out of the inner loop to reduce the module operation.
remove the condition check ( sum != 0).

public int singleNumber(int[] nums) {
    int res = 0;
    for(int i = 0; i < 32; i++){
        int sum = 0;
        for(int n: nums)
            if((n >> i & 1) == 1)
                sum++;
        sum %= 3; // if(sum%3 ==1 => extend to m
        res |= sum<<i;
    }
    return res;
}

Many may wonder what 'a', 'b', 'c' means and how can we manipulate a number like one single bit, as you see in the code, a, b and c are all full 32-bit numbers, not bits. I cannot blame readers to have questions like that because the author did not make it very clear.

In Single Number, it is easy to think of XOR solution because XOR manipulation has such properties:

Commutative: A^B == B^A, this means XOR applies to unsorted arrays just like sorted. (1^2^1^2==1^1^2^2)
Circular: A^B^...^B == A where the count of B's is a multiple of 2.

So, if we apply XOR to a preceding zero and then an array of numbers, every number that appears twice will have no effect on the final result. Suppose there is a number H which appears just once, the final XOR result will be 0^H^...H where H appears as many as in input array.

When it comes to Single Number II (every one occurs K=3 times except one occurs M times, where M is not a multiple of K), we need a substitute of XOR (notated as @) which satisfies:

Commutative: A@B == B@A.
Circular: A@B@...@B == A where the count of B's is a multiple of K.

We need to MAKE the @ operation. This general solution suggests that we maintain a state for each bit, where the state corresponds to how many '1's have appeared on that bit, so we need a int[32] array.

bitCount = [];
for (i = 0; i < 32; i++) {
  bitCount[i] = 0;
}

The state transits like this:

for (j = 0; j < nums.length; j++) {
    n = nums[j];
    for (i = 0; i < 32; i++) {
        hasBit = (n & (1 << i)) != 0;
        if (hasBit) {
            bitCount[i] = (bitCount[i] + 1) % K;
        }
    }
}

I use '!=' instead of '>' in 'hasBit = (n & (1 << i)) != 0;' because 1<<31 is considered negative. After this, bitCount will store the module count of appearance of '1' by K in every bit. We can then find the wanted number by inspecting bitCount.

exept = 0;
for (i = 0; i < 32; i++) {
  if (bitCount[i] > 0) {
    exept |= (1 << i);
  }
}
return exept;

We use bitCount[i] > 0 as condition because there is no tell how many times that exceptional number appears.

Now let's talk about ziyihao's solution. His solution looks much magical than mine because given a fixed K, we can encode the state into a few bits. In my bitCount version, we have a int[32] array to store the count of each bit but a 32-bit integer is way more than what we need to store just 3 states. So ideally we can have a bit[32][2] structure to store the counts. We name bit[...][0] as 'a' and bit[...][1] as 'b' and the bits of n as 'c' and we have ziyihao's post.

The AC Javascript code:

var singleNumber = function(nums) {
    var k, bitCount, i, j, n, hasBit, exept;
    k = 3;
    bitCount = [];
    for (i = 0; i < 32; i++) {
        bitCount[i] = 0;
    }
    for (j = 0; j < nums.length; j++) {
        n = nums[j];
        for (i = 0; i < 32; i++) {
            hasBit = (n & (1 << i)) !== 0;
            if (hasBit) {
                bitCount[i] = (bitCount[i] + 1) % k;
            }
        }
    }
    exept = 0;
    for (i = 0; i < 32; i++) {
      if (bitCount[i] > 0) {
        exept |= (1 << i);
      }
    }
    return exept;
}

这里我们需要重新思考，计算机是怎么存储数字的。考虑全部用二进制表示，如果我们把第 i^th 个位置上所有数字的和对3取余，那么只会有两个结果 0 或 1 (根据题意，3个0或3个1相加余数都为0). 因此取余的结果就是那个 “Single Number”

一个直接的实现就是用大小为 32的数组来记录所有位上的和。

int singleNumber(int A[], int n) {
    int count[32] = {0};
    int result = 0;
    for (int i = 0; i < 32; i++) {
        for (int j = 0; j < n; j++) {
            if ((A[j] >> i) & 1) {
                count[i]++;
            }
        }
        result |= ((count[i] % 3) << i);
    }
    return result;
}


这个算法是有改进的空间的，可以使用掩码变量：

ones   代表第i^th 位只出现一次的掩码变量
twos  代表第i^th 位只出现两次次的掩码变量
threes  代表第i^th 位只出现三次的掩码变量


From http://www.cnblogs.com/daijinqiao/p/3352893.html
对于除出现一次之外的所有的整数，其二进制表示中每一位1出现的次数是3的整数倍，将所有这些1清零，剩下的就是最终的数。
用ones记录到当前计算的变量为止，二进制1出现“1次”（mod 3 之后的 1）的数位。用twos记录到当前计算的变量为止，二进制1出现“2次”（mod 3 之后的 2）的数位。当ones和twos中的某一位同时为1时表示二进制1出现3次，此时需要清零。即用二进制模拟三进制计算。最终ones记录的是最终结果。
int singleNumber(int A[], int n)
{
 int one = 0, two = 0;
 for (int i = 0; i < n; i++)
 {
  two |= A[i] & one;//two 积累值
  one ^= A[i];//one不断求反
  int t = one & two;//第三次的时候one和two都保留了该位的值
  one &= ~t;//清零出现三次的该位的值
  two &= ~t;
 }
 return one;
}


扩展一：


给定一个包含n个整数的数组，除了一个数出现二次外所有的整数均出现三次，找出这个只出现二次的整数。ones记录1出现一次的数，twos记录1出现2次的数，容易知道twos记录的即是最终结果。


扩展二：


给定一个包含n个整数的数组，有一个整数x出现b次，一个整数y出现c次，其他所有的数均出现a次，其中b和c均不是a的倍数，找出x和y。使用二进制模拟a进制，累计二进制位1出现的次数，当次数达到a时，对其清零，这样可以得到b mod a次x，c mod a次y的累加。遍历剩余结果（用ones、twos、fours...变量表示）中每一位二进制位1出现的次数，如果次数为b mod a 或者 c mod a，可以说明x和y的当前二进制位不同（一个为0，另一个为1），据此二进制位将原数组分成两组，一组该二进制位为1，另一组该二进制位为0。这样问题变成“除了一个整数出现a1次（a1 = b 或 a1 = c）外所有的整数均出现a次”，使用和上面相同的方式计算就可以得到最终结果，假设模拟a进制计算过程中使用的变量为ones、twos、fours...那么最终结果可以用ones | twos | fours ...表示。

Also refer to: http://www.cnblogs.com/daijinqiao/p/3352893.html

http://tech-wonderland.net/blog/leetcode-single-number-ii.html

http://oj.leetcode.com/discuss/857/constant-space-solution

http://traceformula.blogspot.com/2015/08/single-number-ii-how-to-come-up-with.html

Read full article from LeetCode-Single Number II[位运算] | Acm之家

LeetCode 137 - Single Number II

Explanation for step 1

Explanation for step 2.

Explanation for step 3.

Labels

Popular Posts