数组中数字出现的次数 II
题目描述
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例：
输入：nums = [3,4,3,3]
输出：4
输入：nums = [9,1,7,9,7,9,7]
输出：1
提示：
1 <= nums.length <= 10000
1 <= nums[i] < 2^31
题目分析
这题目一开始是用哈希表来做的，步骤如下：
- 如果数字不在哈希表里，put进去，value为1
- 如果数字在哈希表里，且value为1，将其更新为2
- 如果数字在哈希表里，且value为2，则将数字移除哈希表
- 遍历完成后，哈希表KeySet里唯一的数字就是出现一次的数字
public int singleNumber(int[] nums) {
HashMap<Integer, Integer> hashMap = new HashMap<>();
for (int num : nums) {
if (hashMap.containsKey(num))
if (hashMap.get(num) == 1)
hashMap.put(num, 2);
else
hashMap.remove(num);
else
hashMap.put(num, 1);
}
return (int) hashMap.keySet().toArray()[0];
}
提交上去之后发现击败了10%的用户，顿时呆了眼，怎么说也是O(N)的算法吧，怎么会这么差（可能是我吃Java不透，造成了过多的性能消耗）！
然后就想着之前做的这一题的easy版本，其他数字出现过两遍，然后根据两个相同数字的异或为0这个天才结论，将所有数字异或的结果返回回去，按道理说升级版的题目应该也能用位运算来做，就开始写写画画...
一个int型数有32位，分别有多少数字在第i位为1，例如【3 3 1 3】序列里，第一位为1的数字有4个，第二位为1的数字有3个，显然，因为第一位%3 != 0，那个唯一的数的第一位就是1，因为没人和它凑成三个1；而第二位%3 == 0，说明那一个唯一的数的第二位不为1；这样就很容易得到唯一的数32个位的具体情况！
public int singleNumber2(int[] nums) {
int now = 1;
int ans = 0;
for (int i = 0; i < 32; i++) {
int cnt = 0;
for (int num : nums) {
if ((num & now) != 0)
cnt++;
}
if (cnt % 3 == 1)
ans |= now;
now <<= 1;
}
return ans;
}
强大的位运算时间复杂度也是O(N)，但是提交上去之后还是傻了眼，只击败58%的人，然后只能乖乖的看题解了；
题解里面有大牛用自动机的理论写了一个短小精悍的代码！感兴趣的可以去搜一下。
最让我不解的是，题解出现了排序方法，我对它进行了一些优化之后竟然击败了80%的用户（Java的内置排序已经优化到O(N)了？）
public int singleNumber3(int[] nums) {
if (nums.length == 1)
return nums[0];
Arrays.sort(nums);
int index = 0;
while (index < nums.length - 1) {
if (nums[index] != nums[index + 1])
return nums[index];
index += 3;
}
return nums[nums.length - 1];
}
排序法
位运算法
哈希表法
