15
3
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? – Emil Vikström – 2014-01-02T01:11:16.540
@EmilVikström See my edit. I meant that you can't use array uniqueness functions. Sorry for being unclear. – hkk – 2014-01-02T01:12:56.317
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 – 2014-01-02T01:18:02.953@O-I The second output is the correct one. The outputted array should have no duplicates. – hkk – 2014-01-02T01:18:49.323
So, I'm guessing simply doing
arr1 | arr2
in Ruby is against the rules? – O-I – 2014-01-02T01:22:27.3471@O-I Yes, that would make it too easy. – hkk – 2014-01-02T01:24:12.313
1May 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 – 2014-01-02T01:30:34.117
@jawns317 Assume that the components of the arrays are primitives- integers, strings, floats, or bools. – hkk – 2014-01-02T01:32:29.377
Does using a function like Mathematica's
DeleteDuplicates
count as a uniqeness function? – Yves Klett – 2014-01-02T08:11:11.567@YvesKlett Yes. That kind of defeats the whole purpose of finding a more efficient algorithm. – hkk – 2014-01-02T15:46:55.450
It need to realize a merge sort with Worst-case performance ~ O(n log n). Boring.
– mazzy – 2018-09-26T09:22:16.687