数组排序 - 和合并 - 算法

我有两个字符串数组：一个有序阵列 - 阵列X，和一个无序的阵列 - 排列Y数组排序 - 和合并 - 算法

什么新的数组应具有：所有项目应该只从数组Y，并且X和Y之间重叠的那些应该根据X中的顺序排序，然后剩下的（如果有的话）应该按照它们最初在Y中的顺序结束。可能的是， X包含不在Y中的条目，我们只是想忽略这些条目。

什么是这样做的有效方式（在PHP中）？

实施例：

阵列X：{ '一个'， 'Z'， 'Q'， 'd'}

阵列Y：{ 'B'， 'C'， 'A'， 'd'， 'Z'}

结果：{ 'A'， 'Z'， 'd'， 'b'， 'C'}

这样的想法是：我们要采取第二数组（数组Y），并根据数组X中给定的顺序对数组中的元素进行排序。由于数组Y可能有更多的额外元素，我们只是想将这些额外的元素放在这个新的结果数组的末尾。说得通？

来源

2012-03-19 user809240

可以给例如输入阵列和一个示例输出？你的解释有点难以遵循。 – Nick 2012-03-19 18:19:39

新增了一个示例，谢谢 – user809240 2012-03-19 18:25:15

你可以这样做：

$result = array(); 

// build index array for constant lookup 
$indexY = array_flip($y); 

// test for each value in X whether it is in Y 
foreach ($x as $valueX) { 
    if (isset($indexY[$valueX])) { 
     $result[] = $valueX; 
     // remove it from the index so we know which values remain 
     unset($indexY[$valueX]); 
    } 
} 

// append remaining values 
foreach ($indexY as $valueY => $i) { 
    $result[] = $valueY; 
}

更新这绝对不是最简洁的解决方案，但是其运行时的复杂性是Ο（ñ），相反，以中提到的其他这里分别为array_intersect，array_diff和array_merge，每个内部对Ο中的数组进行排序（n·log n）。

来源

2012-03-19 18:26:21 Gumbo

谢谢，但这看起来效率不高？这是n^2次，不是吗？ – user809240 2012-03-19 18:42:50

@ user809240不，它实际上只是Ο（* n *），因为索引允许不断的查找时间。 – Gumbo 2012-03-19 18:48:41

<?php 

$intersect = array_intersect($x, $y); 
$diff = array_diff($y, $x); 
$result = array_merge($intersect, $diff); 

?>

来源

2012-03-19 18:29:11

$r = array_merge(array_intersect($x, $y), array_diff($y, $x))

来源

2012-03-19 18:31:30

数组排序 - 和合并 - 算法

回答

相关问题