Алгоритм сортировки и объединения массивов

Question

У меня есть два массива строк: один упорядоченный массив - массив X, и один неупорядоченный массив - массив Y

Что должен иметь новый массив: все элементы должны быть только из массива Y, а те, которые перекрываются между X и Y, должны быть упорядочены на основе порядка в X, а затем остальные (если таковые имеются) должны быть просто в конец в том же порядке, в котором они были изначально в Y. Возможно, X содержит записи, которые не находятся в Y, и мы просто хотим игнорировать их.

Какой эффективный способ сделать это (в php)?

Пример:

Массив X: {'a', 'z', 'q', 'd'}

Массив Y: {'b', 'c', 'a', 'd', 'z'}

Результат: {'a', 'z', 'd', 'b', 'c'}

Итак, идея такова: мы хотим взять 2-й массив (массив Y) и отсортировать элементы в нем в соответствии с порядком, данным нам в массиве X. Поскольку у массива Y может быть больше дополнительных элементов, мы просто хотим поместите эти дополнительные элементы в конец этого нового результирующего массива. Имеет смысл?

Answer 1

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

Answer 2

<?php

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

?>

Answer 3

Вы можете сделать это:

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

---

Обновление Это определенно не самое краткое решение, но его сложность во время выполнения в in ( n ), в отличие от других, упомянутых здесь как array_intersect, array_diff и array_merge внутренне сортируют массивы, находящиеся в Ο ( n · log n ) каждый.