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)

这个算法使用了哈希表来记录数字出现的次数。它的基本思想是遍历整个数组,将每个数字作为键,其出现的次数作为对应的值存储在哈希表中。

具体步骤如下:

  1. 创建一个空的哈希表 counts。
  2. 遍历数组 nums 中的每个数字 num。
  3. 在哈希表 counts 中查找键为 num 的项。如果该项不存在,则将 num 作为键,值初始化为 0。
  4. 将键为 num 的项的值加 1,表示 num 在数组中出现的次数。
  5. 继续遍历数组 nums,直到处理完所有数字。
  6. 遍历哈希表 counts 的每个项,找到值为 1 的项,即只出现一次的数字。
  7. 返回只出现一次的数字。

这个算法的时间复杂度是 O(n),其中 n 是数组的长度。它需要遍历数组两次:一次用于统计数字出现的次数,一次用于找到只出现一次的数字。哈希表的插入和查找操作的时间复杂度是 O(1)。

文章来源:https://blog.csdn.net/m0_62110645/article/details/135171682
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。