高效的算法用于检测匹配

Question

我正在寻找一种高效的算法来检测整数数组N中相等的值。它必须返回匹配项的索引。

不幸的是，我无法想出比使用两个循环更聪明的方法。

任何帮助将不胜感激。 谢谢！

- Nona Urbiz

---

你能给我们一个输入和预期输出的例子吗？这样更容易让我们理解你的意图。 - Alix Axel

此外，在发布问题之前，您可能需要仔细考虑问题和答案的要求。最后一刻的要求只会使事情变得混乱。 - Tyler Carter

@Chacha102，你是对的！我很抱歉！ - Nona Urbiz

我更新了我的回答，提供了另一个选项。这应该是你所要寻找的。 - Tyler Carter

Answer 1

您可以对数组进行交集操作。这将找到array2中与array1相同的所有值。

$array1 = array("a" => "green", "b" => "brown", "c" => "blue", "red");
$array2 = array("a" => "green", "yellow", "red");
$result_array = array_intersect_assoc($array1, $array2);
print_r($result_array);

将返回

Array
(
    [a] => green
)

它返回一个包含所有匹配键和值的数组。基本上，你可以向array_insert_assoc提供无限数量的参数：

array_intersect_assoc($base_array, $arr1, $arr2 ...);

它将在$base_array中搜索所有后续数组中存在的值。这意味着键和值将从$base_array中获取。

您还可以通过使用以下方法比较键：

array_intersect_keys($base_array, $arr1, $arr2, $arr3);

- Tyler Carter

---

不确定，我提到过。但是，你知道它能否返回找到的匹配项的索引吗？ - Nona Urbiz

是的，array_intersect_assoc会这样做。 - Tyler Carter

Answer 2

你可以使用一个集合来保存最近的值。例如：

results = empty list
set = empty set
foreach key, val in array:
   if val is not in set: add val to set
   else: add key to results
return results

每次集合查找都是O(1)，因此如果使用嵌套循环，该算法将产生O(n)而不是O(n^2)。

如果您想跟踪像这个数组1, 2, 3, 3, 2, 1这样的多次出现，可以使用带有键值的哈希表，值（在表中对应键的值）是索引列表。给定数组的结果将看起来像{1:0, 5; 2: 1, 4; 3: 2, 3}。

results = empty hashtable
for each key, val in array:
    if val is not in results:
        results[val] = new list()
    results[val].append(key)
return results

- user247468

---

设置查找和插入通常是O(log N)。 - Jim Lewis

Answer 3

这些循环的时间复杂度为O(N^2)。N很大吗？如果是，您可以使用O(NlogN)对数组进行排序，然后进行O(N)扫描吗？……或者我漏掉了什么吗？

- Mike Dunlavey

---

如果您将每个元素与其原始数组索引配对并一起排序，您可以恢复匹配的任何元素的起始数组索引。 - Jim Lewis

Answer 4

也许是这个？

$arr = array_map('unserialize', array_unique(array_map('serialize', $arr)));

从问题中： 如何在PHP中删除重复的二维数组？

if ($arr !== array_map('unserialize', array_unique(array_map('serialize', $arr))))
{
    // found duplicates
}

- Alix Axel

Answer 5

你不必为每个元素再次遍历整个数组。只需将一个元素与数组中的后续元素进行比较：

$array = /* huge array */;
$size = count($array);
for($i = 0; $i < $size; $i++)
{
    for($j = $i + 1; $j < $size; $j++) // only test with the elements after $i
    {
        if($array[$i] == $array[$j])
            return true; // found a duplicate
    }
    return false; // found no duplicate
}

这是我能想到的最有效的方法。您可以根据自己的需要进行相应调整。

- zneak

Answer 6

如果你的数组中有一个是相对静态的（也就是说，你要多次与同一个数组进行比较），那么你可以将其反转。

也就是说，设置另一个数组，它以值为键，并返回真实数组中的索引。

$invert = array();
foreach ($cmptoarray as $ix => $ival) {
   $invert[$ival] = $ix;
}

然后你只需要一个 if ( isset($invert[$compfrmarray[$i]) ) .... 来检查数字。

注意：只有在多次与同一数组进行比较时才值得这样做！

- James Anderson

Answer 7

只需使用关联数组将值映射到其索引：

foreach($array1 as $index => $value) {
    $aa[$value] = $index;
}

foreach($array2 as $index => $value) {
    if(isset($aa[$value])) {
        echo 'Duplicate:  .  Index 1:  '.$aa[$value].'  Index 2:  '.$index.'.';
    }
}

- dsimcha