數組排序 - 和合並 - 算法

我有兩個字符串數組：一個有序陣列 - 陣列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

數組排序 - 和合並 - 算法

回答

相關問題