题目链接：
剑指 Offer 56 - I. 数组中数字出现的次数
剑指 Offer 56 - II. 数组中数字出现的次数 II
数组中数字出现的次数 题目描述：
一个整型数组 nums text{nums} nums 里除两个数字之外，其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是 O ( n ) O(n) O(n)，空间复杂度是 O ( 1 ) O(1) O(1)。
输入：nums = [4,1,4,6]
输出：[1,6] 或 [6,1]
输入：nums = [1,2,10,4,1,4,3,3]
输出：[2,10] 或 [10,2]
思路：
这题，以及下面的第二题，最大的难度在于 O ( 1 ) O(1) O(1) 的空间复杂度。
如果一个数组，只有一个数出现了一次，其他都出现了两次。那么把它们全部异或起来，最后剩下的就是答案。
但是如果有两个数字都出现一次，异或起来就得到个毫不相干的数。就拿样例1来说，全部异或的答案是 4^6 = 0b010 ，拿到这个数后依然一头雾水。
其实到这里我也不会做了，下面都是看答案的。
如果可以把这一系列数字分成两组，满足：1. 相同的数字分到相同的组。 2. 两个只出现一次的数字分到不同的组。 那么就可以用前面的方法来处理了。
有点像 “取海量数据中出现频率最高的10个单词” 那道题的做法了。海量数据处理的方法总结
言归正传，那么怎么分组呢？
前面得到过一个异或值：4^6 = 0b010。其实根据这个异或值我们还是可以提取少量的信息的：这两个只出现过一次的数字，它们在二进制下第 p p p 位是不同的。（这个例子中，倒数第二位不同）那么，可以根据 arr[i]&(1<<(p-1)) 来将数据分为两组，刚好可以满足上面的两个分组要求。之后再分别将两组数据异或，就得到了要求的这两个数。
class Solution {
public:
vector singleNumbers(vector& array) {
int xorNum=0,div=1,a=0,b=0;
for(int e:array) xorNum^=e;
while(!(xorNum&div)) div<<=1;
for(int e:array){
if(e&div) a^=e;
else b^=e;
}
return {a,b};
}
};
数组中数字出现的次数 题目描述：
在一个数组 nums text{nums} nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。要求时间复杂度是 O ( n ) O(n) O(n)，空间复杂度是 O ( 1 ) O(1) O(1)。
数据范围： 1 < = 1 <= 1<= nums.length text{nums.length} nums.length < = 10000 <= 10000 <=10000， 1 < = 1 <= 1<= nums[i] text{nums[i]} nums[i] < 2 31 < 2^{31} <231
输入：nums = [3,4,3,3]
输出：4
输入：nums = [9,1,7,9,7,9,7]
输出：1
思路：
同样是道内存优化的题，我原本以为第一题理解了以后，做第二题是比较轻松的，但没想到它一题一个做法。这道题我看了看题解，居然提到了有限状态机。
思路是这样的，将每位二进制上，数字出现的次数记录下来。拿样例1来说。二进制下（低三位）每一位出现的次数分别为：1、3、3 。然后将每一位出现的次数 mod text{mod} mod 3，变成 1、0、0 。 再转回十进制，得到答案 4 4 4 。
这个想法成立，但是一个变量它二进制下每一位只能为 0 或 1 ，要实现这个想法，至少每一位要能存 0、1、2 三个数，这一个变量肯定是存不下的。
那，两个变量来存就可以了，处理一下进位方法就可以实现了。
class Solution {
public:
int singleNumber(vector& nums) {
int a=0,b=0;
for(int e:nums){
int t=b&e; b^=t; e^=t;
t=a&e; a|=e; a^=t; b^=t;
}
return a;
}
};
代码层面：先处理高位，再处理低位。假如先处理了低位，那么要根据进位再处理高位，还要再根据高位的进位继续处理低位，比较复杂。
