Algorithme efficace pour détecter les correspondances

Question

Je recherche un algorithme efficace pour détecter des valeurs égales dans un tableau d'entiers de taille N. Il doit retourner les indices des matchs.

Hélas, je ne peux pas penser à quelque chose de plus intelligent, puis la force brute avec deux boucles.

Toute aide sera appréciée. Merci!

Answer 1

Vous pouvez recouper le tableau. Ceci trouve toutes les valeurs de array2 qui sont 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); 

J'y retournerais

Array 
(
    [a] => green 
) 

Il retourne un tableau avec toutes les clés et les valeurs des matches. Fondamentalement, vous pouvez fournir un nombre infini d'arguments à l'array_insert_assoc:

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

Il recherche $base_array pour les valeurs qui sont dans tous les tableaux suivants. Cela signifie que la clé et la valeur seront prises à partir du $base_array

Vous pouvez également comparer les clés en utilisant:

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

Answer 2

Peut-être?

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

de la question: How to remove duplicated 2-dimension array in PHP?

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

Answer 3

Vous ne devez pas passer par tout le tableau à nouveau pour chaque élément. Testez uniquement un élément avec l'élément suivant dans le tableau:

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

C'est le moyen le plus efficace que je puisse penser. Adaptez-le à vos besoins comme vous le voulez.

Answer 4

Ces boucles sont O (N^2). Est-ce que N est grand? Si oui, pouvez-vous trier le tableau O (NlogN), puis le scanner O (N)? ... ou ai-je oublié quelque chose?

Answer 5

Si l'un de vos tableaux est raisonnablement statique (c'est que vous comparez au même tableau plusieurs fois), vous pouvez l'inverser.

Cela définit un autre tableau qui est saisi par valeur et renvoie l'index dans le tableau réel.

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

Ensuite, il vous suffit d'un if (isset($invert[$compfrmarray[$i])) .... pour vérifier le numéro. Remarque: cela ne vaut la peine de faire que si vous comparez plusieurs fois par rapport au même tableau!

Answer 6

Vous pouvez utiliser un ensemble pour conserver les valeurs récentes. Par exemple,

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 

Chaque regard d'ensemble est O (1), donc ce sera algo résultats dans O (n) au lieu de O (n^2) si la boucle imbriquée est utilisée.Dans le cas où vous souhaitez garder une trace de multi-occurrences comme ce tableau 1, 2, 3, 3, 2, 1 vous pouvez utiliser une table de hachage avec la clé est la valeur et la valeur (de la clé correspondante dans le tableau) est la liste des indices. Le résultat pour le tableau donné apparaîtra lik {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 7

il suffit d'utiliser un tableau associatif faisant correspondre une valeur à son indice:

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