# Single Number II

2017-11-27

LeetCode 的一道题，在一个 int 数组中，其余数值均出现了 3 次，只有一个数值出现了 1 次，求这个数： https://leetcode.com/problems/single-number-ii/description/

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?

1. 为 0

2. 为 3 的倍数

3. 为 1

## 位操作法

0 1 2
00 01 10

int 类型的每个比特需要 2 个比特保存状态，一个保存低位比特，一个保存高位比特，那么总共只需要 2 个 int 来保存。接下来要做的就是用 2 个比特模拟 3 进制运算。

### 通过真值表写出逻辑表达式

B A C B’A'
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

$$A'=\overline{B} , \overline{A} , C + \overline{B} , A , \overline{C} =(A\oplus{C}) , \overline{B}$$

$$B'=\overline{B} , C , \overline{A'} + B , \overline{C} , \overline{A'} =(B\oplus{C}) , \overline{A'}$$

int one = 0, two = 0;
for (int i = 0; i < numsSize; ++i) {
one = (one ^ nums[i]) & ~two;
two = (two ^ nums[i]) & ~one;
}


LeetCode算法位操作

Floyd 判圈算法

Gas Station