I want to merge two unsorted arrays and preserve the order of elements in this arrays.

Suppose you have two arrays, and all the elements are unique(no duplicates).

{5,4,2,8,12}
{1,4,8,12,18,36}

the output array should be

{1,5,4,2,8,12,18,36}

We can also store additional info, if item is from first, second, or both arrays.

Any ideas?

I thought Levinstein distance might help here.

If the last two values of the first array are swapped, we should preserve the order according to the second array. The second array ordering is more powerful in this kind of scenarios.

{5,4,2,12,8}
{1,4,8,12,18,36}

still gives

{1,5,4,2,8,12,18,36}

For elements that are not common for two arrays, their order can be arbitrary.

Output array should contain unique values. Every element from two arrays should be listed once only.

CodePudding user response：

One way to achieve this:

• Create a map (hashmap, dictionary) that maps a given value in the first array to its index in that array.

• Create a set (hashset) for the values in the second array (for fast membership tests)

• Iterate the second array and for each value:

  • Check whether it exits in the first array (using the map). If so, it is a duplicate, and then flush all values in that first array up to that occurrence, skipping any value that is duplicate (occurs in B, using the set)

  • Output that value (from B)

• Finally flush any remaining values in A, again skipping those that occur in B (since they were already output)

Here is an implementation in basic JavaScript syntax, running the 2 examples given in the question:

/* Helper function that takes values from the given array and appends them 
 * to the output array. This process starts at the given index i, and
 * continues up to index k, but skipping values that are in
 * the given skipSet. The function returns the updated value of index i.
 */
function flush(a, i, k, skipSet, output) {
    while (i <= k) {
        // If the value in A is not duplicate then output it
        if (!skipSet.has(a[i])) {
            output.push(a[i]);
        }
        i  ;
    }
    return i;
}

function unsortedMerge(a, b) {
    // Map values in A to their index
    let mapA = new Map();
    for (let i = 0; i < a.length; i  ) {
        mapA.set(a[i], i);
    }
    // Create a set of the values in B
    let setB = new Set(b);

    let output = [];
    let i = 0; // index in A
    for (let value of b) { 
        if (mapA.has(value)) { // It's a duplicate
            // Flush all non-duplicate values from A that precede this value 
            i = flush(a, i, mapA.get(value), setB, output);
        }
        // All values in B are guaranteed to be output in their order
        output.push(value);
    }
    // Flush remaining values from A
    flush(a, i, a.length - 1, setB, output);
    return output;
}

// Example runs
console.log(...unsortedMerge([5,4,2,8,12], [1,4,8,12,18,36]));
console.log(...unsortedMerge([5,4,2,12,8], [1,4,8,12,18,36]));

CodePudding user response：

With the array that shall have its order preserved called B and the other one A, Ideas: Either
a) create a set (cheap contains(key)) s from B and append elements a from A if not s.contains(e), only - or
I) append to B the set of elements from A after subtraction of the set of elements from B.

a) sounds promising if A is much smaller than B, only.