Effective Matching Algorithm

Question

I am looking for an efficient algorithm for determining equal values ​​in an array of integers N. It should return match indices.

Alas, I can think of nothing more clever than brute force with two cycles.

Any help would be appreciated. Thanks!

Answer 1

You can cross the array. This finds all the values ​​of array2 that are in array 1

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

Will return

 Array ( [a] => green ) 

It returns an array with all keys and match values. Basically you can provide an infinite number of array_insert_assoc arguments:

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

It will look for $base_array for values ​​that are in all subsequent arrays. This means that the key and value will be taken from $base_array

You can also compare keys using:

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

Answer 2

These loops represent O (N ^ 2). N big? If so, can you sort the O (NlogN) array, then scan its O (N) array? ... or am I missing something?

Answer 3

You can use the set to store the latest values. For instance,

 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 

Each set search is O (1), so this algorithm will output O (n) instead of O (n ^ 2) if a nested loop is used.

If you want to track multiple events like this array 1, 2, 3, 3, 2, 1 , you can use a hash table with a key, this value and the value (of the corresponding key in the table) is a list of indexes. The result for this array will look like {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 4

Perhaps it?

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

From the question: How to remove duplicated 2-dimensional array in PHP?

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

Answer 5

You do not need to traverse the entire array again for each element. Check only the element followed by the element in the array:

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

This is the most effective way that I can think of. Adapt it to your needs, just like you.

Answer 6

If one of your arrays is static enough (that is, you compare the same array several times), you can invert it.

This sets up another array, which is entered by value and returns the index into the real array.

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

Then you just need if ( isset($invert[$compfrmarray[$i]) ) .... check the number.

Note: this is worth doing if you are comparing the same array multiple times!

Answer 7

Just use an associative array matching the value with its index:

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