题目描述
在一个数组 nums 中除一个数字只出现一次之外,其他数字都出现了三次。请找出那个只出现一次的数字。
示例 1:
输入:nums = [3,4,3,3]
输出:4
示例 2:
输入:nums = [9,1,7,9,7,9,7]
输出:1
位运算 + 逐位统计
如果一个数字出现三次,那么它的二进制表示的每一位(0或者1)也出现三次。如果把所有出现三次的数字的二进制表示的每一位都分别加起来,那么每一位的和都能被3整除。如果某一位的和能被3整除,那么那个只出现一次的数字二进制表示中对应的那一位是0;否则就是1;
上述思路同样适用于数组中一个数字出现一次,其他数字出现奇数次问题(如果是偶数次,直接用异或 + 分组 就可)。
这种解法的时间效率是O(n)。我们需要一个长度为32的辅助数组存储二进制表示的每一位的和。由于数组的长度是固定的,因此空间效率是O(1)。
代码实现
class Solution {
public int singleNumber(int[] nums) {//本算法同样适用于数组nums中存在负数的情况
int[] counts = new int[32];//java int类型有32位,其中首位为符号位
for(int num : nums) {
int keyBit = 1;
//因为(num & keyBit)是二进制的第32位,所以j从31开始自减。
for(int j = 31; j >= 0; j--) {
if((num & keyBit)!=0) counts[j]++;
//用上面的代替这个,因为&操作的答案并不是0或者1,就比如110 & 010,答案是2,并不是1。
//counts[j] += num & keyBit;
//这里同样可以通过num的无符号右移>>>来实现,否则带符号右移(>>)左侧会补符号位,对于负数会出错。
//但是不推荐这样做,最好不要修改原数组nums的数据
keyBit = keyBit << 1;//左移没有无符号、带符号的区别,都是在右侧补0
}
}
int res = 0, m = 3;
for(int i = 0; i <32; i++) {
//这两步顺序不能变,否则最后一步会多左移一次
res <<= 1;
res |= counts[31 - i] % m; 或运算操作快速。
//res += counts[i] % m;
}
return res;
}
}
DFS有限自动状态机
请参考以下文章
作者:Krahets
https://leetcode-cn.com/problems/shu-zu-zhong-shu-zi-chu-xian-de-ci-shu-ii-lcof/solution/mian-shi-ti-56-ii-shu-zu-zhong-shu-zi-chu-xian-d-4/
附,二进制运算符~
非运算:~
1取0 0 取1
~1 = 0 ~ 0 = 1
~(1001) = 0110
~按位取反
5二进制00000101,取反11111010,代表-6
所以~5值-6
byte b = 1;
System.out.println(~b);//输出-2 ~运算会将符号位0变为1,1变为0.
System.out.println(b);//输出1.