算法题技巧-Python collections.defaultdict

想利用哈希表存元素个数想起来defaultdict
dict和defaultdic的区别

访问不存在的键：

dict：当访问不存在的键时，会抛出KeyError异常。
defaultdict：当访问不存在的键时，会调用工厂函数返回一个默认值。

1. fruits = {"apple": 2, "banana": 1}
2. print(fruits["orange"])  # KeyError: 'orange'
4. fruit_count = defaultdict(int)
5. print(fruit_count["orange"])  # 输出：0

复制代码

初始化默认值：

dict：需要手动为每个键设置初始值，例如利用setdefault方法。
defaultdict：在创建时通过工厂函数一次性设置所有键的初始值。

1. fruits = {}
2. fruits.setdefault("apple", 0)
3. fruits.setdefault("banana", 0)
5. fruit_count = defaultdict(int)

复制代码

示例标题

https://www.lanqiao.cn/problems/3527/learning/

Ai!的累加效果，A1! + A2! + ... + An!，A1 < A2 < ... < An，则A1!为最大公因数
考虑阶乘的合并情况：有(x+1) * y个x!，能合并为y个(x+1)!。即合成条件为x!的个数为x+1的倍数
利用map存储某个数x的阶乘出现的次数，若到达一定次数，则转换为x+1的阶乘

1. from collections import defaultdict
2. n = int(input())
3. a = list(map(int, input().split()))
4. a.sort()
5. Map = defaultdict(int)
7. for x in a:
8.     Map[x] += 1
10. x = a[0]
11. while True:
12.     cnt = Map[x]
13.     if cnt % (x + 1) == 0:
14.         Map[x + 1] += cnt // (x + 1)
15.         x += 1
16.     else:
17.         print(x)
18.         break

复制代码

免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。