javascript - Most Efficient Way to Find Common Item Between Arbitrary Number of Arrays -
i need able find common item between arbitrary number of arrays. example, let's there's object this:
var obj = { a: [ 15, 23, 36, 49, 104, 211 ], b: [ 9, 12, 23 ], c: [ 11, 17, 18, 23, 38 ], d: [ 13, 21, 23, 27, 40, 85] }; i'd need determine common item between each of these arrays. (in case, 23).
my solution find shortest array, , iterate through each item in it, checking index of other arrays.
var shortest = {}; var keys = []; ( var key in obj ) { if ( obj.hasownproperty( key ) && array.isarray( obj[ key ] ) ) { keys.push( key ); if ( !shortest.hasownproperty( 'length' ) || obj[ key ].length < shortest.length ) { shortest.name = key; shortest.length = obj[ key ].length; } } } var res = obj[ shortest.name ].filter(function ( v ) { ( var = 0; < keys.length; i++ ) { if ( obj[ keys[ ] ].indexof( v ) === -1 ) { return false; } return true; } }; however, seems enormously inefficient, , i'm trying determine if there's better way, preferably without having loop through things multiple times.
i don't think it's possible in less o(n), n number of items in arrays. current solution less efficient, since indexof o(n) each array, , run through of them each item in shortest array.
i think map-based option o(n):
var counts = {}; var keys = object.keys(obj); var arr, el; (var k = 0; k < keys.length; k++) { arr = obj[keys[k]]; (var = 0; < arr.length; i++) { el = arr[i]; if (counts[el] === undefined) { // new value, start counting counts[el] = 1; } else { // increment count value counts[el]++; // if have many values keys, we're done if (counts[el] === keys.length) { return el; } } } } some caveats here:
this assumes elements can used object keys (i.e. can uniquely converted strings), , don't have nasty edge cases
1,"1"in different arrays.this assumes array values unique each array.
this assumes there's 1 element in intersection.
Comments
Post a Comment