在任意个数组之间查找公共项的最有效方法

Question

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]
};

我的解决方案是找到最短的数组，并遍历其中的每个项，检查其他数组的索引。

var shortest = {};
var keys = [];
for ( 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 ) {

  for ( var i = 0; i < keys.length; i++ ) {

    if ( obj[ keys[ i ] ].indexOf( v ) === -1 ) {
      return false;
    }

    return true;
  }
};

然而，这似乎效率极低，我正在尝试确定是否有更好的方法，最好不用多次循环。

Answer 1

我认为不可能在小于O(N)的情况下做到这一点，其中N是所有数组中的项数。您当前的解决方案效率较低，因为indexof对于每个数组都是O(N)，您可以为最短数组中的每个项运行所有的索引。

我认为基于映射的选项应该是O(N):

var counts = {};
var keys = Object.keys(obj);
var arr, el;
for (var k = 0; k < keys.length; k++) {
    arr = obj[keys[k]];
    for (var i = 0; i < arr.length; i++) {
        el = arr[i];
        if (counts[el] === undefined) {
            // new value, start counting
            counts[el] = 1;
        } else {
            // increment count for this value
            counts[el]++;
            // if we have as many values as keys, we're done
            if (counts[el] === keys.length) {
                return el;
            }
        }
    }
}

这里有一些警告：

这假定每个数组的数组值都是唯一的。

假设交集中只有一个元素。

https://jsfidle.net/xzfa75og/