前言
题目限制的死
正文
问题来源
本问题来自leetcode上的137题。
问题描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1:
输入: [2,2,3,2]
输出: 3
示例 2:
输入: [0,1,0,1,0,1,99]
输出: 99
分析：
一般看到这种题,我们第一反应是做状态记录,比如数字x出现了y次.然后从记录里查询出现了一次的数字.但是现在我们的空间复杂度被限制成了O(1),不可能对所有的64位二进制表示的整数进行统计次数.
于是
我们只能着眼于二进制上了,我们先将状态记录缩小到记录目标数字的每一个二进制上.那么这题就会变成遍历所有数,一个二进制位出现1的次数对3取余是否为1,若为1,那么我们目标数字的这一位也就是1.
比如
[1,1,1,2] 他们转换成二进制就是[01,01,01,10],我们可以知道第一位(从右往左)的二进制总共出现了三次1,那么我们的目标结果在第一位就绝对不会是1,相对的第二位出现了一次1,那么我们的目标值在这一位就是1
实际上
这题我们也可以写64个变量(不知道数据量范围多大或者32位也可以?)记录每位的二进制1出现的次数,然后每一个对三取余最后得出的64个1与0再组成一个整数…不过思路本质离不开这里
最后
我们要运用逻辑门的想法设计一个计数器.计数到3就回归0.对于每一个二进制位,出现了多少次1我们可以用两个二进制表示(因为这题只需要记录%3),00表示出现0次,01表示出现1此,10表示出现2次.这样就记录了三个状态,(题目中是出现三次,其实对于x次,我们也可以同理描述).如下
a为高位,b为低位.两个一起表示一个两位二进制表示的数字(一个计数器)
| 计数器代表值 | a | b | 目标出现次数 |
|---|---|---|---|
| 0 | 0 | 0 | 0 |
| 1 | 0 | 1 | 1 |
| 2 | 1 | 0 | 2 |
| 0 | 0 | 0 | 3 |
| 1 | 0 | 1 | 4 |
| 2 | 1 | 0 | 5 |
| … | … | … | … |
上面是我们计数器需要达成的目标,一个计数循环.学过数字电路的同学看到这里应该就知道怎么做了.
我们再进一步. 我们遍历数据,每来一个数据c(这里一个二进制) 我们的a与b就要开始为c计数,那么有以下情况
| a | b | c | 结果a | 结果b |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 0 |
上面比较容易明白,来的是0,那么我们不统计,原来a,b的统计结果不变
| a | b | c | 结果a | 结果b |
|---|---|---|---|---|
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 0 | 0 |
这里也比较容易明白,当来的是1,那么只要为其计数增加1就好.
接下来就是我们的重头戏了.开始设计逻辑门能让我们的计数器保持3个状态记录循环.
我们观察结果a,可以看到会使结果a=1的状态仅有 ( a为1 && b为0 && c为0 ) || (a为0 && b为1 && c为1),同理可以推出b的表达式.
故可得出公式结果a结果b的表达式:
结果a = (a & ~b & ~c) + (~a & b & c)
结果b = (~a & ~b & c) + (~a & b & ~c)
另外根据逻辑代数分配率公式也可以变成:
结果b = ~a & (~b & c + b & ~c) = ~a & (b^c) //二进制进位逻辑
再然后根据上图a,c,结果b 三者的关系写出结果a的逻辑
结果a = a & ~c & (~结果b) + ~a & c & (~结果b) = (~结果b) & (a^c)
然后对实际int型数据做以上处理,就可完成我们的目标.(实际上可以把int看成是在维护一个二进制组成的数组a[i],b[i],c[i],i表示第i位.我们每次位运算操相当于对每一个i所在的三个元素进行操作,也就变成了上述单独描述一个二进制位时的情况.))
public class No137 {
/**
* 如上所推
*/
public static int singleNumber(int[] nums) {
int a = 0, b = 0;
for (int c : nums) {
int tempA = (~a & b & c) + (a & ~b & ~c);
b = (~a & ~b & c) + (~a & b & ~c);
a = tempA;
}
return b;
}
/**
* 如上所推,你也可以写成这样
*/
public int singleNumber(int[] nums) {
int a=0,b=0;
for (int c : nums) {
b = b ^ c & ~ a;
a = a ^ c & ~ b;
}
return b;
}
}
C代码如下：
int singleNumber(int* nums, int numsSize) {
int ones = 0, twos = 0;
for(int i = 0; i < numsSize; i++){
ones = (ones ^ nums[i]) & ~twos;
twos = (twos ^ nums[i]) & ~ones;
}
return ones;
}
int singleNumber(int* nums, int numsSize) {
int x, res = 0;
for(int i = 0; i < sizeof(int) * 8; i++){
x = 1 << i;
int sum = 0;
for(int j = 0; j < numsSize; j++){
if(x & nums[j]) sum++;
}
if(sum % 3) res = res | x;
}
return res;
}
go语言版
func singleNumber(nums []int) int {
ones, twos := 0, 0
for _, v := range nums {
ones = ones ^ v & ^twos
twos = twos ^ v & ^ones
}
return ones
}
Go语言取反方式和C语言不同，Go语言不支持 ~ 符号。
总结：
可怕的位操作。
结语
闲来无事的话，多练习练习，做做题。
