面试题：Python字典与集合在复杂场景下的交集并集操作及优化

Question

假设你有一个大型的字典列表`list_of_dicts = [{'name': 'Alice', 'age': 25, 'skills': ['Python', 'Java']}, {'name': 'Bob', 'age': 30, 'skills': ['C++', 'Python']}, {'name': 'Charlie', 'age': 22, 'skills': ['Python', 'JavaScript']}]`，以及一个技能集合`skill_set = {'Python', 'Ruby'}`。现在需要找出列表中所有技能与技能集合有交集的字典，并优化查找过程，使得在字典列表非常大（例如百万级）时也能高效执行。请给出实现代码，并详细说明优化思路及空间和时间复杂度的分析。

Answer 1

list_of_dicts = [{'name': 'Alice', 'age': 25,'skills': ['Python', 'Java']},
                 {'name': 'Bob', 'age': 30,'skills': ['C++', 'Python']},
                 {'name': 'Charlie', 'age': 22,'skills': ['Python', 'JavaScript']}]
skill_set = {'Python', 'Ruby'}


def find_matching_dicts(lst, skill_set):
    result = []
    for d in lst:
        skills = set(d['skills'])
        if skills.intersection(skill_set):
            result.append(d)
    return result


print(find_matching_dicts(list_of_dicts, skill_set))

优化思路

1. 使用集合操作：在原代码中，将每个字典中的skills列表转换为集合，这样可以利用集合的快速查找特性。intersection方法的时间复杂度为O(min(len(set1), len(set2)))，相比于遍历列表来检查交集，效率大大提高。
2. 空间优化：没有引入额外的与输入规模相关的空间，仅在处理单个字典时，将skills列表转换为集合，这是常数级别的额外空间。

时间复杂度分析

• 假设字典列表长度为n，平均每个字典中的skills列表长度为m。
• 原代码中，遍历字典列表需要O(n)时间，对于每个字典，将skills列表转换为集合需要O(m)时间，计算交集需要O(min(m, len(skill_set)))时间。
• 总体时间复杂度为O(n * (m + min(m, len(skill_set))))，由于m和len(skill_set)相对固定，可近似认为是O(n)。

空间复杂度分析

• 原代码中，除了输入和输出占用的空间，额外使用的空间主要是在处理每个字典时将skills列表转换为集合，这部分空间复杂度为O(m)，是常数级别的额外空间。
• 总体空间复杂度为O(n * m)（输入占用空间） + O(k)（输出占用空间，假设输出字典个数为k） + O(m)（额外空间），近似为O(n * m)。