题目: 只出现一次的数字

题干:

Given a non-empty array of integers, every element appears twice except for one. Find that single one.
Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

中文翻译:

给定一个非空整数数组,除了某个元素只出现一次以外,其余每个元素均出现两次。找出那个只出现了一次的元素。
说明
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗?

Example1:

1
2
输入: [2,2,1]
输出: 1

Example2:

1
2
输入: [4,1,2,1,2]
输出: 4

解题思路

不考虑附加条件

先不看时间复杂度和空间复杂度的限制,解决题干基本要求:找出只出现一次的元素。
将数组中的元素依次取出来,放到一个哈希表中并将其对应的值赋值为0,如果哈希表中已经存在该元素则将哈希表中对应的值加一。
流程图如下:

1
2
3
4
5
6
7
8
9
10
11
st=>start: 依次取出数组中的元素
list_in_hashmap=>condition: 哈希表的key中是否有temp_num
no_in_hashmap=>operation: 哈希表添加key并赋值为0
num_in_hashmap=>operation: 哈希表该key的值自增
over_for=>operation: 循环完,得到哈希表
target=>end: 将哈希表中值为0的key返回

st->list_in_hashmap
list_in_hashmap(yes)->num_in_hashmap->over_for
list_in_hashmap(no)->no_in_hashmap->over_for
over_for->target

代码如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution:
def singleNumber(self, nums: List[int]) -> int:
temp = {}
# 依次取出数组中的元素
for key in nums:
# 哈希表中不存在当前key
if key not in temp:
temp[key] = 0
# 哈希表中已经有当前key
elif key in temp:
# 哈希表对应key的数值+1
temp[key] = temp[key] + 1
# target = 哈希表中值为0的key
for key in temp:
if(temp[key] == 0):
target = key
return target

添加附属条件的解法

题目附加中,要求算法应该具有线性时间复杂度并且尽量不用额外空间,也就是说时间复杂度要尽量满足 O(x)。
题目标签中有位运算和哈希表两个,目前只用了哈希表因此估计附加条件需要用到位运算来解决。
位运算我只是粗略的了解过,为此我深入的了解了一下位运算。
位运算二进制运算,其中异或运算最适合该题。 异或运算的规则是:

  1. 任何数和 0 做异或运算,结果仍然是原来的数,即 a ⊕ 0 = a
  2. 任何数和其自身做异或运算,结果是 0, 即 a ⊕ a = 0
  3. 个人总结
    • 二进制中,相同为 0 不同为 1
    • 十进制中,相同为 0 不同为 自身

用图来解释:

代码如下:

1
2
3
4
5
6
7
class Solution:
def singleNumber(self, nums: List[int]) -> int:
target = 0
# 遍历一次,并将每个元素依次进行异或运算
for key in nums:
target = target ^ key
return target

参考资料

LeetCode: https://leetcode-cn.com/