### 题目

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?

### 利用HashMap，时间复杂度 $O(n)$，空间复杂度 $O(n)$

#### 代码

public class Solution {
public int singleNumber(int[] nums) {
Map<Integer,Integer> memo = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
Integer remain = memo.get(nums[i]);
if (remain == null) {
memo.put(nums[i],2);
} else if (remain > 1) {
memo.replace(nums[i],remain-1);
} else if (remain == 1) {
memo.remove(nums[i]);
}
}
int res = 0;
for (Map.Entry<Integer,Integer> entry : memo.entrySet()) {
res = entry.getKey();
}
return res;
}
}


public class Solution {
public int singleNumber(int[] nums) {
Set<Integer> members = new HashSet<>();
Set<Integer> duplicates = new HashSet<>();
for (int i = 0; i < nums.length; i++) {
Integer num = nums[i];
if (!duplicates.contains(num)) {
}
}
}
members.removeAll(duplicates);
return (int)members.toArray()[0];
}
}


### 用XOR收集信息，时间复杂度 $O(n)$，空间复杂度 $O(n)$

#### 代码

public class Solution {
public int singleNumber(int[] nums) {
Map<Integer,Integer> memo = new HashMap<>();
int res = 0;
for (int i = 0; i < nums.length; i++) {
Integer num = nums[i];
res ^= nums[i];
if (memo.get(num) == null) {
memo.put(num,0);
} else {
memo.remove(num);
res ^= nums[i];
}
}
return res;
}
}


public class Solution {
public int singleNumber(int[] nums) {
Map<Integer,Integer> members = new HashMap<>();
Map<Integer,Integer> duplicates = new HashMap<>();
int res = 0;
for (int i = 0; i < nums.length; i++) {
res ^= nums[i];
int num = nums[i];
if (!duplicates.containsKey(num)) {
if (members.put(num,0) != null) {
duplicates.put(num,0);
res ^= nums[i];
}
}
}
return res;
}
}


### 收集每一位上1出现的次数

0, 0, 0, 0, 0, 1, 0, 1  // 5
0, 0, 0, 0, 0, 0, 1, 1  // 3
0, 0, 0, 0, 0, 1, 0, 0  // 4
0, 0, 0, 0, 0, 0, 1, 0  // 2
0, 0, 0, 0, 0, 1, 0, 0  // 4
0, 0, 0, 0, 0, 0, 1, 1  // 3
0, 0, 0, 0, 0, 0, 1, 0  // 2
0, 0, 0, 0, 0, 0, 1, 1  // 3
0, 0, 0, 0, 0, 0, 1, 0  // 2
0, 0, 0, 0, 0, 0, 0, 1  // 1
0, 0, 0, 0, 0, 1, 0, 0  // 4
0, 0, 0, 0, 0, 1, 0, 1  // 5
------------------------------------------
0, 0, 0, 0, 0, 6, 6, 7  // 每位上1出现的次数


#### 代码

public class Solution {
public int singleNumber(int[] nums) {
int[] bitCount = new int[32];
for (int num : nums) { // 收集每一位上1的信息
for (int i = 0, mask = 1; i < 32; i++, num = num >> 1) {
int eachBit = num & mask;
if (eachBit == 1) {
bitCount[i] = bitCount[i] + 1;
}
}
}
int res = 0;
for (int i = 0, mask = 1; i < 32; i++, mask = mask << 1) {
if (bitCount[i] % 3 != 0) { // 读取每一位上1的信息
res = res | mask; // 把信息写到答案上
}
}
return res;
}
}


### 更聪明的办法收集每一位上1出现次数

01010101
01010101 ^
----------
00000000


1. 当一个数字出现第一次，会在b中体现它的信息。
2. 当它出现第二次，会在a中体现它的信息。
3. 当它出现第三次，它的信息将彻底消失。

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


a=~abc+a~b~c;

b=~a~bc+~ab~c;

#### 代码

public class Solution {
public int singleNumber(int[] nums) {
//  1. 当一个数字出现第一次，会在b中体现它的信息。
//  2. 当它出现第二次，会在a中体现它的信息。
//  3. 当它出现第三次，它的信息将彻底消失。
//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;
}
//b中是只出现一次数字的所有信息。
return b;

}
}