实现数量特定的数组交集：解决array_intersect的重复值问题

开发者阿泽

2026-8-25

PHP 数组交集（保留重复项最小数量）

出于优化需求，需要对两个数组求交集，结果数组需保留两个原数组中重复值的最小数量，元素顺序无关紧要。由于要在大循环中执行，时间复杂度是核心约束。

为什么`array_intersect`不适用？

根据PHP文档中Shawn Pyle的说明：

array_intersect对数组中的重复项处理方式不同。若第一个数组存在重复项，所有匹配的重复项都会被返回；若后续数组存在重复项，则不会返回这些重复项。

需求规则

返回$arr1中存在于$arr2的元素
若$arr1或$arr2包含重复值，返回两者中数量较少的那部分

示例

intersect([1, 1, 2, 3, 4, 4, 5], [1, 3, 3, 5, 5]) 返回 [1, 3, 5]
intersect([1, 1, 2, 3, 4, 4, 5], [1, 1, 1, 3, 3, 5, 5]) 返回 [1, 1, 3, 5]
intersect([1, 1, 2, 3, 4, 4, 5, 5], [1, 3, 3, 5, 5]) 返回 [1, 3, 5, 5]
intersect([1, 1, 1], [1, 1, 1]) 返回 [1, 1, 1]
intersect([1, 2, 3], [1, 3, 2]) 返回 [1, 2, 3]

高效实现方案

要满足大循环场景的时间要求，采用统计元素频次的方案，整体时间复杂度为O(n+m)，具体实现代码如下：

function intersect(array $arr1, array $arr2): array {
    // 统计两个数组的元素出现频次
    $counts1 = array_count_values($arr1);
    $counts2 = array_count_values($arr2);
    
    $result = [];
    foreach ($counts1 as $value => $count) {
        if (isset($counts2[$value])) {
            // 取当前元素在两个数组中出现次数的最小值
            $minCount = min($count, $counts2[$value]);
            // 将元素重复对应次数加入结果数组
            for ($i = 0; $i < $minCount; $i++) {
                $result[] = $value;
            }
        }
    }
    
    return $result;
}