题目描述
这是 LeetCode 上的 137. 只出现一次的数字 II 。
Tag : 「哈希表」、「位运算」
给你一个整数数组 nums ，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次 。
请你找出并返回那个只出现了一次的元素。
示例 1：
输入：nums = [2,2,3,2] 输出：3 复制代码
示例 2：
输入：nums = [0,1,0,1,0,1,99] 输出：99 复制代码
提示：
- 1 <= nums.length <= 3 * 10410^4104
- -2312^{31}231 <= nums[i] <= 2312^{31}231 - 1
- nums 中，除某个元素仅出现 一次 外，其余每个元素都恰出现 三次
进阶：你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
哈希表
一个朴素的做法是使用「哈希表」进行计数，然后将计数为 111 的数字进行输出。
哈希表以「数值 : 数值出现次数」形式进行存储。
代码：
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(n)O(n)O(n)
位数统计
哈希表解法的空间复杂度是 O(n)O(n)O(n) 的，而题目的【进阶】部分提到应当使用常数空间来做。
其中一个比较容易想到的做法，是利用 intintint 类型固定为 323232 位。
使用一个长度为 323232 的数组 cnt[]cnt[]cnt[] 记录下所有数值的每一位共出现了多少次 111，再对 cnt[]cnt[]cnt[] 数组的每一位进行 modmodmod333 操作，重新拼凑出只出现一次的数值。
举个 🌰，考虑样例 [1,1,1,3]，111 和 333 对应的二进制表示分别是 00..001 和 00..011，存入 cnt[]cnt[]cnt[] 数组后得到 [0,0,...,0,1,4]。进行 modmodmod333 操作后得到 [0,0,...,0,1,1]，再转为十进制数字即可得「只出现一次」的答案 333。
代码：
class Solution { public int singleNumber(int[] nums) { int[] cnt = new int[32]; 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) { ans += (1 << i); } } return ans; } } 复制代码
- 时间复杂度：O(n)O(n)O(n)
- 空间复杂度：O(1)O(1)O(1)
DFA
如果我们考虑「除了某个元素只出现一次以外，其余每个元素均出现两次」的情况，那么可以使用「异或」运算。
利用相同数异或为 0 的性质，可以帮助我们很好实现状态切换：
本题是考虑「除了某个元素只出现一次以外，其余每个元素均出现三次」的情况，那么对应了「出现 0 次」、「出现 1 次」和「出现 2 次」三种状态，意味着至少需要两位进行记录，且状态转换关系为：
那么如何将上述 DFA 用表达式表示出来呢？有以下几种方法：
- 用「真值表」写出「逻辑函数表达式」可参考 这里，化简过程可以参考 卡诺图化简法 。
- 把结论记住（这是一道经典的 DFA 入门题）。
- 硬做，位运算也就那几种，不会「数字电路」也记不住「结论」，砸时间看着真值表不断调逻辑也是可以写出来的。
代码：
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; } } 复制代码
- 时间复杂度：O(n)O(n)O(n)
- 空间复杂度：O(1)O(1)O(1)
最后
这是我们「刷穿 LeetCode」系列文章的第 No.137 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先将所有不带锁的题目刷完。
在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。
为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：github.com/SharingSour…
在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。
