Problem: 137. 只出现一次的数字 II
文章目录
- 思路
- 💖 哈希
- 💖 位数统计
- 💖 DFA 状态机
思路
👨🏫 参考
💖 哈希
⏰ 时间复杂度:
O
(
n
)
O(n)
O(n)
🌎 空间复杂度:
O
(
n
)
O(n)
O(n)
class Solution {
public int singleNumber(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
for (int x : nums) {
map.put(x, map.getOrDefault(x, 0) + 1);
}
for (int x : map.keySet()) {
if (map.get(x) == 1) return x;
}
return -1;
}
}
// 作者：宫水三叶
💖 位数统计
⏰ 时间复杂度:
O
(
n
)
O(n)
O(n)
🌎 空间复杂度:
O
(
1
)
O(1)
O(1)
class Solution {
public int singleNumber(int[] nums)
{
int[] cnt = new int[32]; // 记录每个数的每个位出现了多少个 1
for (int x : nums)
for (int i = 0; i < 32; i++)
if (((x >> i) & 1) == 1)
cnt[i]++;
int ans = 0;
for (int i = 0; i < 32; i++)
if ((cnt[i] % 3 & 1) == 1)// 3 个一组消去
ans += (1 << i);
return ans;
}
}
💖 DFA 状态机
⏰ 时间复杂度:
O
(
n
)
O(n)
O(n)
🌎 空间复杂度:
O
(
1
)
O(1)
O(1)
class Solution {
public int singleNumber(int[] nums) {
int one = 0, two = 0;
for(int x : nums){
one = one ^ x & ~two;
two = two ^ x & ~one;
}
return one;
}
}
//作者：宫水三叶
