力扣面试150 只出现一次的数字Ⅱ 哈希 统计数位 DFA有穷自动机

Problem: 137. 只出现一次的数字 II

思路

👨‍🏫 参考

💖 哈希

⏰ 时间复杂度: $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(1)$

class Solution {public int singleNumber(int[] nums){int[] cnt = new int[32];		// 记录每个数的每个位出现了多少个 1for (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(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;}
}//作者：宫水三叶