M

tags: Bit Manipulation

一串数字里面, 所有数字都重复三次, 除了一个数字. 找到这个数字, linear time, without extrace space (constant space)

TODO: bits

```

/*

Given a non-empty 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?

Example 1:

Input: [2,2,3,2]

Output: 3

Example 2:

Input: [0,1,0,1,0,1,99]

Output: 99

*/

/*

Given 3*n + 1 numbers, every numbers occurs triple times except one, find it.

Example

Given [1,1,2,3,3,3,2,2,4,1] return 4

Challenge

One-pass, constant extra space

Thinking process:

Still using bit manipulation. We need to erase all of the 3-appearance number and leave the single number out. A few steps:

Store the final result by continuously bit OR with the result variable.

Want to XOR the 3 numbers, but can’t erase them as if only 2 duplicate numbers:Consider the number as 3-based number, so XOR can be understand this way

when add 3 numbers together, add each individual bit. If the sum is 3, then set it as 0. If not 3, leave as is.

3. Store the bits in a integer array, which simulates a binary version of the integer

4. When each bit’s XOR process finishes, bit OR it with result

*/

class Solution {

public int singleNumber(int[] A) {

if (A == null || A.length == 0) {

return -1;

}

//present the XOR results in binary format

int[] bits = new int[32];

int rst = 0;

for (int i = 0; i < 32; i++) {

for (int j = 0; j < A.length; j++){

//XOR the numbers in a 3-base fashion. Whenever bit[i] has a number 3, set it back to 0.

bits[i] += A[j] >> i & 1;

bits[i] %= 3;

}

//OR it to the result. However, each time only the i - spot is updated with the bits[i].

rst |= bits[i] << i;

}

return rst;

}

}

```