Array Merge without Duplicates

  • I recently saw this Javascript code on StackOverflow for merging two arrays, and removing duplicates:



    Array.prototype.unique = function() {
    var a = this.concat();
    for(var i=0; i<a.length; ++i) {
    for(var j=i+1; j<a.length; ++j) {
    if(a[i] === a[j])
    a.splice(j--, 1);
    }
    }
    return a;
    };

    var array1 = ["Vijendra","Singh"];
    var array2 = ["Singh", "Shakya"];
    var array3 = array1.concat(array2).unique();


    While this code works, it is horribly inefficient (O(n^2)). Your challenge is to make an algorithm with less complexity.



    The winning criteria is the solution with the least complexity, but ties will be broken by shortest length in characters.



    Requirements:



    Package all your code together in a function that meets the following requirements for "correctness:"




    • Input: Two arrays

    • Output: One array

    • Merges elements of both arrays together- Any element in either input array must be in the outputted array.

    • The outputted array should have no duplicates.

    • Order doesn't matter (unlike the original)

    • Any language counts

    • Don't use the standard library's array functions for detecting uniqueness or merging sets/arrays (although other things from the standard library is okay). Let me make the distinction that array concatenation is fine, but functions that already do all of the above are not.


    How are we supposed to create or append to an array without using array functions?

    @EmilVikström See my edit. I meant that you can't use array uniqueness functions. Sorry for being unclear.

    If one of the arrays has duplicates in it, do we remove them as well? For example, should merging `[1, 2, 2, 3]` and `[2, 3, 4]` return `[1, 2, 2, 3, 4]` or `[1, 2, 3, 4]`?

    @O-I The second output is the correct one. The outputted array should have no duplicates.

    So, I'm guessing simply doing `arr1 | arr2` in Ruby is against the rules?

    @O-I Yes, that would make it too easy.

    May I ask: Arrays of _what_? Can we assume simply integers or strings, or do we also have to allow more complex things like multilevel objects?

    @jawns317 Assume that the components of the arrays are primitives- integers, strings, floats, or bools.

    Does using a function like Mathematica's `DeleteDuplicates` count as a uniqeness function?

    @YvesKlett Yes. That kind of defeats the whole purpose of finding a more efficient algorithm.

    It need to realize a merge sort with Worst-case performance ~ O(n log n). Boring.

  • Perl

    27 Characters



    Simple Perl Hack



    my @vals = ();
    push @vals, @arr1, @arr2;
    my %out;
    map { $out{$_}++ } @vals;
    my @unique = keys %out;


    I'm sure someone could one-liner this.. and thus (Thanks Dom Hastings)



    sub x{$_{$_}[email protected]_;keys%_}

    "Don't use the standard library's array functions for detecting uniqueness (although other things form the standard library is okay)"

    How I am violating that rule? I'm not using unique functions?

    How does it work, then? Sorry, I can't read perl. If it reads the keys of a hash map - does that count as OK with that rule? I won't vote until convinced that it is.

    It combines the arrays, loops over both and adds to a hash incrementing the value who's key is the current value in the array loop. Then it takes the keys of that hash, I have used this in some of my work.. So [1,1,2,3,4,4] becomes { 1 => 2, 2 => 1, 3 => 1, 4 => 2 }

    @ZachLeighton you can shorten the code to 27 chars with `sub x{$_{$_}[email protected]_;keys%_}` (in case it comes down to a tie!) and use as: `z((1,2,3,4),(2,3,4,5,6))`

    I saw your answer above.. very nicely done.

    I've removed my answer, I didn't realise you'd already submitted a Perl solution. Please feel free to utilise this golfed version.

    Sure I referenced you in the edit, thanks!

    A bit late to the party: `sub x{keys{map{$_,1}@_}}` for 24. The original could also be improved by one by replacing `$_{$_}++` with `\$_{$_}`.

License under CC-BY-SA with attribution


Content dated before 7/24/2021 11:53 AM