首页
学习
活动
专区
圈层
工具
发布
社区首页 >问答首页 >用最小重复值交叉两个数组

问用最小重复值交叉两个数组
EN

Stack Overflow用户
提问于 2022-07-26 08:43:33
回答 2查看 57关注 0票数 1

为了达到优化的目的,我需要交叉两个数组,并在结果数组中保留两个初始数组中最少的重复值。

结果数组中值的顺序并不重要。

另一个重要的限制是时间复杂性,因为这将在一个大循环中执行。

为什么array_intersect不能工作:

From in the PHP docs :

array_intersect以不同的方式处理数组中的重复项。如果第一个数组中有重复项,则将返回所有匹配的重复项。如果后续的任何数组中都有重复项,则不会返回它们。

规则:

  • 返回$arr2
  • 中的$arr1值,如果$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]
EN

回答 2

Stack Overflow用户

发布于 2022-07-26 09:59:43

嗨,首先我得说@Aderrahim的答案看起来很不错,但是后来我尝试使用简单的方法来测试性能。

以下是代码:

代码语言:javascript
复制
function intersectSimple($a, $b)
{
    $result = array();
    $short = count($a) < count($b) ? $a : $b;
    $long = count($a) < count($b) ? $b : $a;
    foreach ($short as $v) {
        if (in_array($v, $long)) {
            //if found add to results and remove from b
            $result[] = $v;
            unset($long[array_search($v, $long)]);
        }
    }
    return $result;
}

function intersectAderrahim($a, $b)
{
    $a_values_count = array_count_values($a);
    $b_values_count = array_count_values($b);

    $res = array_values(array_intersect($a, $b));
    $res_values_count = array_count_values($res);
    foreach ($res as $key => $val)
    {
        if ($res_values_count[$val] > $a_values_count[$val] || $res_values_count[$val] > $b_values_count[$val])
        {
            unset($res[$key]);
            $res_values_count[$val]--;
        }
    }

    return array_values($res);
}

//Start timer
$start = microtime(true);

echo "Start Test\n";
//Test code print each assert result
//Run code 100000 times
for ($i = 0; $i < 100000; $i++)
{
    $a = array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
    $b = array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
    $result = intersectSimple($a, $b);
    assert(count($result) == 10);
}

//Stop timer
$end = microtime(true);
$time = $end - $start;
//Print performance in microseconds
echo "Performance Simple: $time\n";

//Start timer
$start = microtime(true);

echo "Start Test\n";
//Test code print each assert result
//Run code 100000 times
for ($i = 0; $i < 100000; $i++)
{
    $a = array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
    $b = array(1, 2, 3, 4, 5, 6, 7, 8, 9, 10);
    $result = intersectAderrahim($a, $b);
    assert(count($result) == 10);
}
//Stop timer
$end = microtime(true);
$time = $end - $start;
//Print performance in microseconds
echo "Performance Aderrahim: $time\n";

因此,我编写了一个快速性能测试并运行它,结果如下:

代码语言:javascript
复制
Start Test
Performance Simple: 0.060362815856934
Start Test
Performance Aderrahim: 0.16634893417358

我不知道这是否可以推断到一个真实的情况,但您可以尝试您的场景和测试哪个更好。我真的很想知道真实数据中哪一个是最好的。

票数 1
EN

Stack Overflow用户

发布于 2022-07-26 08:57:29

这是我的尝试,如果可能的话,我基本上是在寻找一种更快的方法来做到这一点:

代码语言:javascript
复制
function intersect($a, $b)
{
    $a_values_count = array_count_values($a);
    $b_values_count = array_count_values($b);

    $res = array_values(array_intersect($a, $b));
    $res_values_count = array_count_values($res);
    foreach ($res as $key => $val)
    {
        if ($res_values_count[$val] > $a_values_count[$val] || $res_values_count[$val] > $b_values_count[$val])
        {
            unset($res[$key]);
            $res_values_count[$val]--;
        }
    }

    return array_values($res);
}

assert(intersect([1, 1, 2, 3, 4, 4, 5], [1, 3, 3, 5, 5]) == [1, 3, 5]);
assert(intersect([1, 1, 2, 3, 4, 4, 5], [1, 1, 1, 3, 3, 5, 5]) == [1, 1, 3, 5]);
assert(intersect([1, 1, 2, 3, 4, 4, 5, 5], [1, 3, 3, 5, 5]) == [1, 3, 5, 5]);
assert(intersect([1, 1, 1], [1, 1, 1]) == [1, 1, 1]);
assert(intersect([1, 2, 3], [1, 3, 2]) == [1, 2, 3]);
票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/73120276

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档