Эффективный алгоритм обнаружения совпадений

Question

Я ищу эффективный алгоритм для обнаружения равных значений в массиве целых чисел N размера. Должен возвращать индексы совпадений.

Увы, я не могу придумать ничего более умного, чем грубая сила с двумя петлями.

Любая помощь будет оценена. Спасибо!

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);

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

Answer 3

Эти петли O (N ^ 2). N большой? Если да, можете ли вы отсортировать массив O (NlogN), а затем сканировать его O (N)? ... или я что-то упустил?

Answer 4

Просто используйте ассоциативный массив, сопоставляющий значение с его индексом:

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.'.';
    }
}

Answer 5

Если один из ваших массивов достаточно статичен (то есть вы сравниваете один и тот же массив несколько раз), вы можете инвертировать его.

Это устанавливает другой массив, который имеет ключ по значению и возвращает индекс в реальный массив.

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

Тогда вам просто нужно if ( isset($invert[$compfrmarray[$i]) ) ...., чтобы проверить номер.

Примечание: это стоит делать, только если вы сравниваете один и тот же массив несколько раз!

Answer 6

Вам не нужно снова проходить весь массив для каждого элемента. Тестируйте только элемент с последующим элементом в массиве:

$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
}

Это самый эффективный способ, который я могу придумать. Приспособьте его к своей необходимости, как пожелаете.

Answer 7

Возможно это?

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

Из вопроса: Как удалить дублированный двумерный массив в PHP?

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