面试题：Python字典与集合用法的高级问题

Question

有两个字典 `dict1 = {'a': 1, 'b': 2, 'c': 3}` 和 `dict2 = {'b': 20, 'c': 30, 'd': 40}`，编写一个函数，该函数接收这两个字典作为参数，返回一个新字典，新字典包含两个输入字典中所有的键值对，如果某个键在两个字典中都存在，则将对应的值相加。同时，有一个集合 `set1 = {1, 2, 3}` 和 `set2 = {3, 4, 5}`，如何高效地获取两个集合的对称差集，并分析使用不同方法的时间复杂度。

Answer 1

def merge_dicts(dict1, dict2):
    result = dict1.copy()
    for key, value in dict2.items():
        if key in result:
            result[key] += value
        else:
            result[key] = value
    return result

set1 = {1, 2, 3}
set2 = {3, 4, 5}
symmetric_difference = set1.symmetric_difference(set2)

获取两个集合对称差集使用 symmetric_difference 方法，其时间复杂度为 $O(len(set1) + len(set2))$。因为集合查找元素的时间复杂度是 $O(1)$，所以遍历两个集合所有元素来计算对称差集，时间复杂度与两个集合元素数量之和相关。

关于合并字典函数 merge_dicts，先复制 dict1 时间复杂度为 $O(len(dict1))$，遍历 dict2 时间复杂度为 $O(len(dict2))$，在 dict1 中查找键时间复杂度为 $O(1)$，所以整体时间复杂度为 $O(len(dict1) + len(dict2))$。