面试题：Python字典与集合复杂交集并集操作

Question

给定两个字典`dict_a = {'x': {'inner_key1': 10, 'inner_key2': 20}, 'y': {'inner_key3': 30}, 'z': {'inner_key4': 40}}`和`dict_b = {'x': {'inner_key1': 15, 'inner_key5': 25}, 'z': {'inner_key4': 45, 'inner_key6': 55}}`，将它们看作特殊的集合（键值对视为集合元素），请编写代码求出这两个“集合”的交集，即相同键且内层字典至少有一个相同的键值对。要求以合理的数据结构返回结果，并对代码的时间复杂度进行分析。

Answer 1

dict_a = {'x': {'inner_key1': 10, 'inner_key2': 20}, 'y': {'inner_key3': 30}, 'z': {'inner_key4': 40}}
dict_b = {'x': {'inner_key1': 15, 'inner_key5': 25}, 'z': {'inner_key4': 45, 'inner_key6': 55}}

result = {}
for key in set(dict_a.keys()) & set(dict_b.keys()):
    inner_result = {}
    for inner_key, inner_value in dict_a[key].items():
        if inner_key in dict_b[key] and dict_b[key][inner_key] == inner_value:
            inner_result[inner_key] = inner_value
    if inner_result:
        result[key] = inner_result

print(result)

时间复杂度分析

1. 求外层字典键的交集：set(dict_a.keys()) & set(dict_b.keys())，假设dict_a和dict_b分别有m和n个键，将字典的键转换为集合时间复杂度为$O(m)$和$O(n)$，求集合交集时间复杂度为$O(min(m, n))$，总体为$O(m + n)$。
2. 内层循环：对于每个外层字典的公共键，假设内层字典平均长度为k，内层循环的时间复杂度为$O(k)$，总共有$O(min(m, n))$个公共键，所以这部分时间复杂度为$O(min(m, n) * k)$。

综合起来，整个算法的时间复杂度为$O(m + n + min(m, n) * k)$。当m和n相近，且k相对较小的情况下，时间复杂度近似为$O(m * k)$ 。