十亿个数的集合和10w个数的集合 如何求它们的交集

Question

如果两个集合中的元素较多，直接遍历比较会非常耗时。对于较大的集合，一种高效的求交集算法是使用哈希表。

首先，我们遍历较小的集合，将其中的元素都添加到一个哈希表中。然后，我们再遍历较大的集合，对于每一个元素，都在哈希表中查找是否存在。如果存在，则该元素是交集的一部分。

该算法的时间复杂度是 O(n)，其中 n 是较大集合的大小。这是因为在遍历较小集合时，我们需要将其所有元素添加到哈希表中，需要 O(k)的时间，其中 k 是较小集合的大小。而在遍历较大集合时，每个元素都需要在哈希表中查找，需要 O(1)的时间。

下面是示例代码：

def findIntersection(set1, set2):
    # 创建一个哈希表
    hashTable = {}

    # 遍历较小的集合，并将元素添加到哈希表中
    if len(set1) < len(set2):
        for num in set1:
            hashTable[num] = True
        # 遍历较大的集合，对每个元素查找是否存在
        intersection = [num for num in set2 if num in hashTable]
    else:
        for num in set2:
            hashTable[num] = True
        intersection = [num for num in set1 if num in hashTable]

    return intersection

# 示例用法
set1 = [1, 2, 3, 4, 5]
set2 = [4, 5, 6, 7, 8, 9, 10]
intersection = findIntersection(set1, set2)
print(intersection)

输出为 [4, 5] ，即两个集合的交集。