LeetCode 137. Single Number II [Medium]

发表于 更新于 分类于 ， 阅读次数：

LeetCode 137. Single Number II

题目来源：https://leetcode.com/problems/single-number-ii

题目难度：Medium

核心思想

一个 int 型整数有32个二进制位。

  • 对于每个二进制位，统计这一位上1的个数，然后对3取余，如果余数不为0，说明不重复的那个数的这个二进制位为1。
  • 统计每一位上1的个数，通过和二进制1进行位与操作。
  • 如果某个二进制位是1，通过和结果进行 或 操作，把这个1添加到结果中对应的二进制位上。

解答1[Java]：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int singleNumber(int[] nums) {
        int result = 0;
        for (int i = 0; i < 32; ++i) {
            int sum_of_j_digit = 0;
            for (int j = 0; j < nums.length; ++j) {
                sum_of_j_digit += (nums[j] >> i) & 1;
            }

            result |= (sum_of_j_digit % 3) << i;
        }

        return result;
    }
}

解答2[Java]：有限状态机

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int singleNumber(int[] nums) {
        int a = 0, b = 0;
        
        for (int num : nums) {
            b = b ^ num & ~a;
            a = a ^ num & ~b;
        }
        
        return a|b;
    }
}

最后一句 return 语句如果改为 return b; 也可以得到正确结果。

不过这个算法，同样是有限状态机，其实有好几个写法，不过核心应该都是做一个三进制的计数器。我觉得对我而言是真的很难理解，现在也没有完完全全理解。这里先把几个解释的帖子记下来，等到有时间再来攻克。

An General Way to Handle All this sort of questions.

Detailed explanation and generalization of the bitwise operation method for single numbers

Leetcode 136, 137, 260 “Single Number”-s - unnamed42’s blog

LeetCode-137：Single Number II (只出现一次的数字)