PHP阵列密钥对值转移的复杂性问题

Question

我有2个数组。 array1和array2是相同的，除了array2的子阵列没有键'key3'并且子阵列的顺序不匹配。

$array1=array(
    0=>array(
     'type'=>'1' 
     'id'=>'1' 
     'key3'=>'abc' 
     ) 
    1=>array(
     'type'=>'1' 
     'id'=>'2' 
     'key3'=>'def' 
     ) 
    3=>array(
     'type'=>'2' 
     'id'=>'1' 
     'key3'=>'ghi' 
     ) 
    ... 
) 
$array2=array(
    0=>array(
     'type'=>'1' 
     'id'=>'1' 
     ) 
    1=>array(
     'type'=>'2' 
     'id'=>'1' 
     ) 
    ... 
) 

该任务只是简单地把key3和它的值放到array2对应的子数组中。

我只能想到几个层次的foreach循环来实现的任务，这将是非常昂贵的

是否有可以执行的任务更简单更快什么方法呢？

Answer 1

// build a hash table of id/type => key3 for fast access 
$index = array(); 
foreach ($array1 as $data) { 
    $index[$data['id'].'/'.$data['type']] = $data['key3']; 
} 

// use that hash table 
foreach ($array2 as &$data) { 
    $data['key3'] = $index[$data['id'].'/'.$data['type']]; 
} 
// never forget to unset the variable if iterating by reference 
unset($data); 

为什么这是快：你只有两个与N次迭代，其中N界定的元素个数循环，所以这是复杂O(N)的。哈希访问被认为是O(1)。所以整个复杂性是线性的。嵌套循环迭代将是O(N^2)。