Array Merge without Duplicates
JavaScript O(N) 131 124 116 92 (86?)
Golfed version:
function m(i,x){h={};n=[];for(a=2;a--;i=x)i.map(function(b){h[b]=h[b]||n.push(b)});return n}
Human readable golfed version:
function m(i,x) {
h = {}
n = []
for (a = 2; a--; i=x)
i.map(function(b){
h[b] = h[b] || n.push(b)
})
return n
}
I could use concat
like so and do it in 86 characters:
function m(i,x){h={};n=[];i.concat(x).map(function(b){h[b]=h[b]||n.push(b)});return n}
But I am not sure if it is still O(N) based on this JsPerf: http://jsperf.com/unique-array-merging-concat-vs-looping as the concat version is marginally faster with smaller arrays but slower with larger arrays (Chrome 31 OSX).
In practice do this (golf is full of bad practices):
function merge(a1, a2) {
var hash = {};
var arr = [];
for (var i = 0; i < a1.length; i++) {
if (hash[a1[i]] !== true) {
hash[a1[i]] = true;
arr[arr.length] = a1[i];
}
}
for (var i = 0; i < a2.length; i++) {
if (hash[a2[i]] !== true) {
hash[a2[i]] = true;
arr[arr.length] = a2[i];
}
}
return arr;
}
console.log(merge([1,2,3,4,5],[1,2,3,4,5,6]));
I'm not great at computing complexity but I believe this is O(N)
. Would love if someone could clarify.
Edit: Here is a version that takes any number of arrays and merges them.
function merge() {
var args = arguments;
var hash = {};
var arr = [];
for (var i = 0; i < args.length; i++) {
for (var j = 0; j < args[i].length; j++) {
if (hash[args[i][j]] !== true) {
arr[arr.length] = args[i][j];
hash[args[i][j]] = true;
}
}
}
return arr;
}
console.log(merge([1,2,3,4,5],[1,2,3,4,5,6],[1,2,3,4,5,6,7],[1,2,3,4,5,6,7,8]));
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{$_{$_}++for@_;keys%_}
Python 2.7, 38 chars
F=lambda x,y:{c:1 for c in x+y}.keys()
Should be O(N) assuming a good hash function.
Wasi's 8 character set
implementation is better, if you don't think it violates the rules.