up vote 0 down vote favorite

I have two array of strings: one ordered array - Array X, and one unordered array - array Y

What the new array should have: all items should only be from array Y, and the ones that overlap between X and Y should be ordered based on the order in X, and then the rest (if any) should just be at the end in the same order as they were originally in Y. It is possible that X contains entries that are not in Y, and we just want to ignore those.

What is an efficient way of doing this (in php)?

Example:

Array X: {'a', 'z', 'q', 'd'}

Array Y: {'b', 'c', 'a', 'd', 'z'}

Result: {'a', 'z', 'd', 'b', 'c'}

So the idea is: we want to take the 2nd array (array Y), and sort the elements in it based on the ordering given to us in array X. Since Array Y might have more extra elements, we just want to put those extra elements at the end of this new resultant array. Makes sense?

share|improve this question
27% accept rate
can you give example input arrays and an example output? Your explanation is a bit hard to follow. – Nick Mar 19 at 18:19
Added an example, thanks – user809240 Mar 19 at 18:25
feedback

3 Answers

up vote 3 down vote 
$r = array_merge(array_intersect($x, $y), array_diff($y, $x))
share|improve this answer
feedback
up vote 1 down vote 
<?php

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

?>
share|improve this answer
feedback
up vote 1 down vote

You can do this:

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

Update  This is definitely not the most concise solution, but its runtime complexity is in Ο(n), in opposite to the others mentioned here as array_intersect, array_diff, and array_merge sort the arrays internally that is in Ο(n·log n) each.

share|improve this answer
thanks, but that does not seem very efficient? It's n^2 time, isn't it? – user809240 Mar 19 at 18:42
@user809240 No, it’s actually just Ο(n) due to the index which allows constant lookup time. – Gumbo Mar 19 at 18:48
feedback

Your Answer

 
or
required, but never shown
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.