只出现一次的数字数据结构与算法实验报告
时间: 2023-12-03 22:42:45 浏览: 38
实验目的:
掌握使用哈希表解决只出现一次的数字问题的基本思路与方法。
实验原理:
只出现一次的数字问题可以使用哈希表来解决。具体步骤如下:
1. 遍历整个数组,将每个数字作为 key,出现的次数作为 value 存入哈希表中。
2. 再次遍历整个数组,找到 value 为 1 的 key,即为只出现一次的数字。
3. 如果哈希表中没有 value 为 1 的 key,说明没有只出现一次的数字。
实验步骤:
1. 创建一个哈希表,将数组中每个数字作为 key,出现的次数作为 value 存入哈希表中。
2. 遍历哈希表,找到 value 为 1 的 key,即为只出现一次的数字。
3. 如果哈希表中没有 value 为 1 的 key,说明没有只出现一次的数字。
实验代码实现:
```python
def find_only_once(nums):
hashtable = {}
# 将每个数字作为 key,出现的次数作为 value 存入哈希表中
for num in nums:
if num not in hashtable:
hashtable[num] = 1
else:
hashtable[num] += 1
# 遍历哈希表,找到 value 为 1 的 key,即为只出现一次的数字
for key, value in hashtable.items():
if value == 1:
return key
# 如果哈希表中没有 value 为 1 的 key,说明没有只出现一次的数字
return None
```
实验结果:
对于数组 [1, 2, 2, 3, 3, 4, 4, 5, 5],只出现一次的数字为 1。
对于数组 [1, 1, 2, 2, 3, 3, 4, 4, 5],只出现一次的数字为 5。
对于数组 [1, 1, 2, 2, 3, 3, 4, 4, 5, 5],没有只出现一次的数字。
实验结论:
使用哈希表可以解决只出现一次的数字问题,时间复杂度为 O(n),空间复杂度为 O(n)。