- 题目描述
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
示例1：
输入：nums = [3,4,3,3] 输出：4
示例2：
输入：nums = [9,1,7,9,7,9,7] 输出：1二、分析 方法1：hashMap统计个数，遍历返回
比较常规的思路就是通过hashMap统计个数，然后遍历返回即可。思路简单，但这种方法显示没有充分利用题中的条件其他数字都出现了三次。所以一定不是最优解。
方法2：位运算 分析其他数字出现了三次，这是我们解题的突破点。
做这种数字题，我们要有位运算的思想在，所以我们绞尽脑汁往位运算那边去靠。我们试想一下，如果将所有数字转换为二进制，然后观察一下会有什么规律呢？如下：
nums=[4,4,4,5,5,5,3]
出现3次：4,5
* 4:0100b
* 4:0100b
* 4:0100b
* 5:0101b
* 5:0101b
* 5:0101b
出现1次：3
* 3:0011b
我们发现4,5这两个重复的数字每一位之和必定是3的倍数，道理很简单，因为相同的数字出现了3次，多个相同的数之和肯定是3的倍数。
利用这个规律，每位和是三的倍数，我们将所有数字每位求和，然后模3，就是出现一次数字的对应位。如下：
nums=[4,4,4,5,5,5,3]
出现3次：4,5
* 4:0100b
* 4:0100b
* 4:0100b
* 5:0101b
* 5:0101b
* 5:0101b
* 3:0011b
每位进行sum%3结果就是要求的数，如下：
* 3:0011b
复杂度
时间O(N)
两次遍历O(32)*O(N)
空间O(1)常数辅助遍历O(1)
三、代码 方法1：hashMap统计个数，遍历返回
public static int singleNumber(int[] nums) {
HashMap hashMap = new HashMap();
int j=0;
for (int i : nums) {
// j=hashMap.get(i)==null?1:hashMap.get(i)+1;//可以优化，因为我们只要计数为1的key,超过1的key我们可以直接设置为-1。减少get操作。
j=hashMap.get(i)==null?1:-1;//优化减少get操作。
hashMap.put(i,j);
}
for (Integer i : hashMap.keySet()) {
if (hashMap.get(i)==1) return i;
}
return -1;
}
方法1小优化，避免计数
public static int singleNumberB(int[] nums) {
HashMap hashMap = new HashMap<>();
for (int i : nums) {
hashMap.put(i,hashMap.containsKey(i));
}
for (Integer i : hashMap.keySet()) {
if (hashMap.get(i)==false) return i;
}
return -1;
}
方法2：位运算
public static int singleNumberA(int[] nums) {
int sum;//所有数字某个位置之和
int res=0;//结果
for (int j = 0; j <32; j++) {
sum=0;
for (int i = 0; i < nums.length; i++) {
sum += ( (nums[i] >> j) & 1);//用"&1" 和每位测试是1或0
}
res +=( (sum%3) << j);
}
return res;
}
四、总结
这道题用位运算可以拓展到其他数字重复n次，具有一定的通解性。本质上利用转换为二进制之后，通过取余运算，找到独一无二的数。
位运算常见性质总结:
0 or 任何数等于其本身 0 xor 任何数等于其本身（本题用到性质） 1 and 任何数等于其本身（本题用到性质） 0 and 任何数等于0 1 or 任何数等于1 1 xor 任何数等于本身取反
