如何获取两个数组的精确重叠元素（匹配元素重复次数）

嘿，这个需求我之前处理过，普通的数组交集操作（比如Python里的set(a1) & set(a2)）确实只能返回去重后的元素，完全满足不了要保留最小重复次数的要求。我觉得用哈希表统计元素出现频率是最优的解决办法，效率高还容易理解，具体思路和实现如下：

核心思路 #

1. 分别统计两个数组中每个元素的出现次数，这样我们就能明确每个元素在各自数组里的重复次数。
2. 遍历其中一个统计结果的元素，对于同时存在于两个统计结果里的元素，取两个数组中该元素出现次数的最小值。
3. 把这个元素重复对应次数，添加到结果数组里。

代码实现（Python） #

如果用Python的话，可以直接用内置的collections.Counter来快速统计频率，代码非常简洁：

from collections import Counter

a1 = [1, 1, 1, 2, 3, 3, 3]
a2 = [1, 1, 3, 3, 5, 5]

# 统计两个数组的元素频率
counter_a1 = Counter(a1)
counter_a2 = Counter(a2)

result = []
for num in counter_a1:
    # 只处理两个数组都有的元素
    if num in counter_a2:
        # 取出现次数的最小值，扩展到结果数组
        result.extend([num] * min(counter_a1[num], counter_a2[num]))

print(result)  # 输出: [1, 1, 3, 3]

要是不想用内置库，手动实现频率统计也很简单：

def get_frequency(arr):
    freq = {}
    for num in arr:
        freq[num] = freq.get(num, 0) + 1
    return freq

a1 = [1, 1, 1, 2, 3, 3, 3]
a2 = [1, 1, 3, 3, 5, 5]

freq_a1 = get_frequency(a1)
freq_a2 = get_frequency(a2)

result = []
for num in freq_a1:
    if num in freq_a2:
        result.extend([num] * min(freq_a1[num], freq_a2[num]))

print(result)

为什么这是最优解？ #

这个方法的时间复杂度是O(n + m)，其中n和m是两个数组的长度——统计频率是线性遍历，遍历频率字典也是线性操作，比那种嵌套循环查找元素的O(n*m)高效太多，尤其是当数组规模比较大的时候，优势特别明显。

如果你的数组已经是排序好的，也可以用双指针的方法，但如果数组未排序，先排序的时间复杂度是O(n logn + m logm)，反而不如哈希表方法高效，所以哈希表统计频率是通用的最优方案。

内容的提问来源于stack exchange，提问作者Naoki Mi