Python算法例24 落单的数Ⅱ
2023-12-23 19:13:58
1. 问题描述
给出3n+1个非负整数元素的数组,除其中一个数字之外,其他每个数字均出现三次,找到这个数字。
2. 问题示例
给出[1,1,2,3,3,3,2,2,4,1],返回4。
3. 代码实现
使用哈希表实现
def find_single_number(nums):
counts = {}
for num in nums:
counts[num] = counts.get(num, 0) + 1
for num, count in counts.items():
if count == 1:
return num
# 从输入获取数组
input_str = input("请输入数组,以逗号分隔:")
nums = list(map(int, input_str.split(',')))
# 调用函数并输出结果
result = find_single_number(nums)
print("只出现一次的数字是:", result)
这个算法使用了哈希表来记录数字出现的次数。它的基本思想是遍历整个数组,将每个数字作为键,其出现的次数作为对应的值存储在哈希表中。
具体步骤如下:
- 创建一个空的哈希表 counts。
- 遍历数组 nums 中的每个数字 num。
- 在哈希表 counts 中查找键为 num 的项。如果该项不存在,则将 num 作为键,值初始化为 0。
- 将键为 num 的项的值加 1,表示 num 在数组中出现的次数。
- 继续遍历数组 nums,直到处理完所有数字。
- 遍历哈希表 counts 的每个项,找到值为 1 的项,即只出现一次的数字。
- 返回只出现一次的数字。
这个算法的时间复杂度是 O(n),其中 n 是数组的长度。它需要遍历数组两次:一次用于统计数字出现的次数,一次用于找到只出现一次的数字。哈希表的插入和查找操作的时间复杂度是 O(1)。
文章来源:https://blog.csdn.net/m0_62110645/article/details/135171682
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。 如若内容造成侵权/违法违规/事实不符,请联系我的编程经验分享网邮箱:veading@qq.com进行投诉反馈,一经查实,立即删除!