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