[Leetcode] 137.只出现一次的数字 II

[Acceml]

题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现了三次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,3,2]
输出: 3

示例 2:

输入: [0,1,0,1,0,1,99]
输出: 99

题解

根据上一道题目的经验，我们很明确的知道不能用数数字的办法去解。考虑位运算的办法，找相关的性质。

这个题其实就是求，在其他数都出现 k 次的数组中有一个数只出现一次，求出这个数。

而上面那个 k 次的是有通用解法的。

使用一个 32 维的数组，用这个 32 维的数组存储:

[第 31 位 1 的总数， 第 30 位 1 的个数，…， 第 1 位 1 的个数]

• 假如第 0 位 1 的个数是 k 的倍数，那么要求的这个数在该位一定是 0 ；

• 若不是 k 的倍数，那么要求的这个数在该位一定是 1。

  因为假如说数组中的某些数在该位置是 1，那么因为这个数要么出现 k 次，那么出现 1 次。

这样我们就可以找出只出现一次那个数的二进制表示形式。二进制如何转化为 10 进制呢？

假如，按照上面的规则，最招找到的二进制为:

A = [0, 0, 0, 0, 0, …, 1]

因为异或操作是：相同为 0，不同为 1。

那么久可以依次用 1, 2, 4, 8 … 和依次每一位异或，即可得到最终答案。

第二部分可能不好理解，可以手动模拟下。

class Solution {
    public int singleNumber(int[] nums) {
        // 有多少个相同的数字
        int N = 3;
        // [高位 1 的个数,...,低位 1 的个数]
        int[] bitNum = new int[32];
        
        for (int i = 0; i < nums.length; i++) {
            int compare = 1;
            int num = nums[i];
            for (int j = bitNum.length - 1; j >= 0; j--) {
                if ((compare&num) != 0) {
                    bitNum[j]++;
                }
                compare = compare << 1;
            }
        }
        
        int compare = 1;
        int res = 0;
        for(int i = bitNum.length - 1; i >= 0; i--) {
            if(bitNum[i] % N != 0) {
                res = res ^ compare;
            }
        }
        return res;
   }
}

热门阅读

• 看了很多技术书，为啥仍然写不出项目？
• [ Spring ] IOC 是啥有什么好处
• 百度社招面试题—— Redis 实现分布式锁
• [ Leetcode ] 114. 二叉树展开为链表

[wenzhoou]

@xml123 楼上一句话就说出了本质。

[Yyyye]

@azh7138m 能不能解释下这个

[EthanDon]

模 3 加法，可以的

[azh7138m]

@Yyyye 和最佳答案一个意思，就是一个 0 -> 1 -> 2 -> 0 的状态循环
现在做我肯定选三个变量那个最优解
4 年过去了，我的数电早还给老师了（

[azh7138m]

@Yyyye 看了楼上的模 3 加法我想起来了…….
o t 是 one 第一位 two 第二位的意思，其实就是实现了一个模 3 加法，所以算完只要把第一位的 one 返回出去就好了
就是 00 01 10 三个状态的转移
对于 one 假如高位不是 1，输入是 1，那就是 00 -> 01 就是 o^(*it) ，高位是 1 的时候，如果这次输入是 1，那么应该是 10 -> 00 就是 &(~(t&*it)) 这里对高位做了判断
对于 two 如果高位和输入都是 1，那么就是 10 -> 00，所以是 ~(t&(*it)) ，对于其他的情况，~(t&(*it)) 结果都是 1，就看低位会不会进位，所以是 o&*it，最后 |t 是，高位是 1 低位是 0 输入是 0 对应这个场景
oo 是因为我要先算 o，要保存一下
大概就是这么个意思，我记得是枚举出所有的情况，写到一个表上，然后画电路图（
这玩意我记得拿逻辑门做汽车尾灯花式闪烁上用到过（

[churchmice]

@azh7138m 卡诺图

[Yyyye]

@azh7138m 看来要学习下数电了

[azh7138m]

@churchmice 好像是这个，唉都忘记了。。。

[qwertyegg]

也写了个 solution
~~~
public class Solution137 {
public int singleNumber(int[] nums) {
int[] bits = new int[32];
for(int n : nums)
addBits(n, bits);
StringBuilder binarySB = new StringBuilder();
for(int i = 31; i >= 0; i--) {
binarySB.append(bits[i] % 3);
}
return (int)Long.parseLong(binarySB.toString(), 2);
}
private void addBits(int n, int[] bits){
int i = 0;
while(n != 0){
bits[i] += n % 2;
i++;
n = n >>> 1;
}
}
}
~~~

[qwertyegg]

也写了个 solution(上面的 markdown 错了)
```
public class Solution137 {
public int singleNumber(int[] nums) {
int[] bits = new int[32];
for(int n : nums)
addBits(n, bits);
StringBuilder binarySB = new StringBuilder();
for(int i = 31; i >= 0; i--) {
binarySB.append(bits[i] % 3);
}
return (int)Long.parseLong(binarySB.toString(), 2);
}
private void addBits(int n, int[] bits){
int i = 0;
while(n != 0){
bits[i] += n % 2;
i++;
n = n >>> 1;
}
}

public static void main(String[] args) {
System.out.println(new Solution137().singleNumber(new int[]{-2,-2,1,1,-3,1,-3,-3,-4,-2}));

}
}
```

[qwertyegg]

orz，跪了！

[valleyboy]

求和 取余 右移 数制转换 循环