배열을 정렬 - 및 병합 - 알고리즘

Question

내가 문자열의 두 배열이 하나 순서 배열 - 배열 X, 하나 개의 정렬되지 않은 배열 - 배열 Y

새로운 배열이 있어야 무엇

: 모든 항목은 배열되어야한다 Y와 X와 Y 사이에 중첩되는 것들은 X의 순서에 따라 정렬되어야하고 나머지는 Y에 원래 있었던 순서대로 끝나야합니다. X는 Y에없는 항목을 포함하므로 무시해야합니다.

이 작업을 수행하는 효율적인 방법은 무엇입니까?

예 :

어레이 X { 'A', 'Z', 'Q', 'D'}

어레이 Y : { 'B', 'C', 'A', 'D', 'Z'}

결과 : { 'A', 'Z', 'D', 'B', 'C'}

그래서 아이디어는 : 우리가 2 위를 먹고 싶어 배열 Y (배열 Y)를 만들고, 배열 X에서 우리에게 주어진 순서에 따라 요소를 정렬합니다. 배열 Y는 더 많은 요소를 가질 수 있으므로 이러한 새로운 요소의 끝에 추가 요소를 넣기 만하면됩니다. 말이된다?

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

---

업데이트이 확실히 가장 간결한 해결책이 아니다, 그러나 그것의 실행의 복잡성은 언급 된 다른 사람에게 반대에, Ο (N)에 있습니다

Answer 1

이 작업을 수행 할 수 있습니다 여기서 array_intersect, array_diff 및 array_merge은 배열을 내부적으로 정렬합니다 (ø (n · 로그 n).

Answer 2

<?php 

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

?> 

Answer 3

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