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 (只出现一次的数字)