LeetCode面试题题系列的上一篇文章 Leetcode面试系列 第1天：Leetcode 89 - 格雷码 中，我们介绍了 二进制相关 的一个典型题。
今天呢，咱们来聊聊哈希表(字典)，这是另一种典型面试题。哈希表实际上就是用内存空间换时间，即消耗额外的一点内存，但可将数据存取的时间大大降低，其时间复杂度几乎是常数时间(O(1))。
比较典型的一个问题是 Leetcode 上第 136 号问题，
Leetcode 136. Single number
在线提交地址: https://leetcode-cn.com/problems/single-number/
题目描述
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。你可以不使用额外空间来实现吗？
示例 1:
输入:[2,2,1]输出:1
示例 2:
输入:[4,1,2,1,2]输出:4
- 贡献者: LeetCode
- 题目难度: Easy
相关话题
相似题目
- 只出现一次的数字 II 难度: 中等
https://leetcode-cn.com/problems/single-number-ii/
- 只出现一次的数字 III 难度: 中等
https://leetcode-cn.com/problems/single-number-iii/ - 缺失数字 难度: 简单
https://leetcode-cn.com/problems/missing-number/ - 寻找重复数 难度: 中等
https://leetcode-cn.com/problems/find-the-duplicate-number/
解题思路:
解法1:
使用字典 dict 存储每一个整数出现的次数，如果当前数在 dict 中不存在，则添加之，出现的次数设置成1，否则每再出现一次，次数加1。最后从里面挑出第一个出现次数为1的 KeyValuePair 的 Key 值即可。
解法2:
使用按位异或。
由于异或操作^具有如下几个性质：
- a^a = 0
- a^0 = a
- a^b = b^a
那么，将原 nums 数组里的所有数进行按位异或，每两个相等的数都异或为 0 而抵消了，最后剩下的数与 0 异或得到的是它本身，即为只出现过一次的数。
方法1的已 AC 代码(Python 3):
classSolution:def singleNumber(self, nums:List[int])-> int:res =0d = dict()for num in nums:if num notin d:d[num]=1else:d[num]+=1res = next(k for k, val in d.items()if val ==1)return res
如果需要在本地测试，需要先在代码开头引入 fromtypingimportList。完整代码如下:
from typing importListclassSolution:def singleNumber(self, nums:List[int])-> int:res =0d = dict()for num in nums:if num notin d:d[num]=1else:d[num]+=1res = next(k for k, val in d.items()if val ==1)return res#以下是测试sol =Solution()print(sol.singleNumber([6,4,6,2,4]))
运行结果:
执行用时: 104ms, 在所有 Python3 提交中击败了 43.71%的用户。
方法2的已 AC 代码(Python 3):
classSolution:def singleNumber(self, nums:List[int])-> int:r =0for i in nums:r ^= ireturn r
如果需要本地测试，其方法与 方法1 类似，只需要替换 class 部分即可。
运行结果:
执行用时: 84ms, 在所有 Python 3 提交中击败了 99.96%的用户。
显然，对于此题， 位运算依然更胜一筹。
