javascript - js数组交集 - js数组补集




在javascript中最简单的数组交集 (20)

在javascript中实现数组相交的最简单,无库代码是什么? 我想写

intersection([1,2,3], [2,3,4,5])

并得到

[2, 3]

采用ES2015的功能性方法

功能性方法必须考虑只使用纯功能而没有副作用,每个功能都只涉及一项工作。

这些限制增强了所涉及功能的可组合性和可重用性。

// small, reusable auxiliary functions

const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
const apply = f => x => f(x);


// intersection

const intersect = xs => ys => {
  const zs = createSet(ys);
  return filter(x => zs.has(x)
     ? true
     : false
  ) (xs);
};


// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];


// run it

console.log( intersect(xs) (ys) );

请注意,使用本机Set类型,它具有有利的查找性能。

避免重复

显然,第一个Array中的重复出现的项目将被保留,而第二个Array被重复删除。 这可能是或可能不是期望的行为。 如果您需要唯一的结果,请将dedupe应用于第一个参数:

// auxiliary functions

const apply = f => x => f(x);
const comp = f => g => x => f(g(x));
const afrom = apply(Array.from);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));


// intersection

const intersect = xs => ys => {
  const zs = createSet(ys);
  return filter(x => zs.has(x)
     ? true
     : false
  ) (xs);
};


// de-duplication

const dedupe = comp(afrom) (createSet);


// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];


// unique result

console.log( intersect(dedupe(xs)) (ys) );

计算任意数量的Array的交集

如果你想计算一个任意数量的Arrayintersect ,只需要与foldl intersect 。 这是一个方便的功能:

// auxiliary functions

const apply = f => x => f(x);
const uncurry = f => (x, y) => f(x) (y);
const createSet = xs => new Set(xs);
const filter = f => xs => xs.filter(apply(f));
const foldl = f => acc => xs => xs.reduce(uncurry(f), acc);


// intersection

const intersect = xs => ys => {
  const zs = createSet(ys);
  return filter(x => zs.has(x)
     ? true
     : false
  ) (xs);
};


// intersection of an arbitrarily number of Arrays

const intersectn = (head, ...tail) => foldl(intersect) (head) (tail);


// mock data

const xs = [1,2,2,3,4,5];
const ys = [0,1,2,3,3,3,6,7,8,9];
const zs = [0,1,2,3,4,5,6];


// run

console.log( intersectn(xs, ys, zs) );


  1. 把它分类
  2. 从索引0逐个检查,从中创建新的数组。

像这样的东西,虽然没有很好地测试。

function intersection(x,y){
 x.sort();y.sort();
 var i=j=0;ret=[];
 while(i<x.length && j<y.length){
  if(x[i]<y[j])i++;
  else if(y[j]<x[i])j++;
  else {
   ret.push(x[i]);
   i++,j++;
  }
 }
 return ret;
}

alert(intersection([1,2,3], [2,3,4,5]));

PS:该算法仅用于Numbers和Normal Strings,任意对象数组的交集可能不起作用。


Coffeescript中N个数组的交集

getIntersection: (arrays) ->
    if not arrays.length
        return []
    a1 = arrays[0]
    for a2 in arrays.slice(1)
        a = (val for val in a1 when val in a2)
        a1 = a
    return a1.unique()

.filter生成一张地图,并找到.filter找到交集。 在.filter delete允许我们把第二个数组看作是一个唯一的集合。

function intersection (a, b) {
  var seen = a.reduce(function (h, k) {
    h[k] = true;
    return h;
  }, {});

  return b.filter(function (k) {
    var exists = seen[k];
    delete seen[k];
    return exists;
  });
}

我觉得这种方法很容易推理。 它持续执行。


使用Array.prototype.filterArray.prototype.indexOf的组合。

array1.filter(function(n) {
    return array2.indexOf(n) !== -1;
});

使用Underscore.js

_.intersection( [0,345,324] , [1,0,324] )  // gives [0,324]

使用ES2015和套件很短。 接受像类似字符串的类似数组的值并删除重复项。

let intersection = function(a, b) {
  a = new Set(a), b = new Set(b);
  return [...a].filter(v => b.has(v));
};

console.log(intersection([1,2,1,2,3], [2,3,5,4,5,3]));

console.log(intersection('ccaabbab', 'addb').join(''));


另一种可以同时处理任意数量数组的索引方法:

// Calculate intersection of multiple array or object values.
function intersect (arrList) {
    var arrLength = Object.keys(arrList).length;
        // (Also accepts regular objects as input)
    var index = {};
    for (var i in arrList) {
        for (var j in arrList[i]) {
            var v = arrList[i][j];
            if (index[v] === undefined) index[v] = 0;
            index[v]++;
        };
    };
    var retv = [];
    for (var i in index) {
        if (index[i] == arrLength) retv.push(i);
    };
    return retv;
};

它仅适用于可以作为字符串进行评估的值,并且应该将它们作为数组传递,如下所示:

intersect ([arr1, arr2, arr3...]);

...但它透明地接受对象作为参数或任何要相交的元素(总是返回通用值数组)。 例子:

intersect ({foo: [1, 2, 3, 4], bar: {a: 2, j:4}}); // [2, 4]
intersect ([{x: "hello", y: "world"}, ["hello", "user"]]); // ["hello"]

编辑:我只是注意到,这是,在某种程度上,稍有越野车。

那就是:我编码它认为输入数组本身不能包含重复(如所提供的示例不)。

但是如果输入数组碰巧包含重复,那会产生错误的结果。 示例(使用以下实现):

intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]);
// Expected: [ '1' ]
// Actual: [ '1', '3' ]

幸运的是,通过简单地添加二级索引,这很容易解决。 那是:

更改:

        if (index[v] === undefined) index[v] = 0;
        index[v]++;

通过:

        if (index[v] === undefined) index[v] = {};
        index[v][i] = true; // Mark as present in i input.

...和:

         if (index[i] == arrLength) retv.push(i);

通过:

         if (Object.keys(index[i]).length == arrLength) retv.push(i);

完整的例子:

// Calculate intersection of multiple array or object values.
function intersect (arrList) {
    var arrLength = Object.keys(arrList).length;
        // (Also accepts regular objects as input)
    var index = {};
    for (var i in arrList) {
        for (var j in arrList[i]) {
            var v = arrList[i][j];
            if (index[v] === undefined) index[v] = {};
            index[v][i] = true; // Mark as present in i input.
        };
    };
    var retv = [];
    for (var i in index) {
        if (Object.keys(index[i]).length == arrLength) retv.push(i);
    };
    return retv;
};

intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]); // [ '1' ]

如果您的环境支持ECMAScript 6 Set ,则可以使用一种简单并且效率很高的方法(请参阅规范链接):

function intersect(a, b) {
  var setA = new Set(a);
  var setB = new Set(b);
  var intersection = new Set([...setA].filter(x => setB.has(x)));
  return Array.from(intersection);
}

更短,但可读性更差(也不需要创建额外的交集):

function intersect(a, b) {
      return [...new Set(a)].filter(x => new Set(b).has(x));
}

请注意,集合实现将只允许唯一值,因此new Set[1,2,3,3].size计算结果为3


对于只包含字符串或数字的数组,您可以按照其他一些答案进行排序。 对于任意对象数组的一般情况,我不认为你可以避免漫长的过程。 以下将给出作为参数提供给arrayIntersection的任意数量的数组的arrayIntersection

var arrayContains = Array.prototype.indexOf ?
    function(arr, val) {
        return arr.indexOf(val) > -1;
    } :
    function(arr, val) {
        var i = arr.length;
        while (i--) {
            if (arr[i] === val) {
                return true;
            }
        }
        return false;
    };

function arrayIntersection() {
    var val, arrayCount, firstArray, i, j, intersection = [], missing;
    var arrays = Array.prototype.slice.call(arguments); // Convert arguments into a real array

    // Search for common values
    firstArray = arrays.pop();
    if (firstArray) {
        j = firstArray.length;
        arrayCount = arrays.length;
        while (j--) {
            val = firstArray[j];
            missing = false;

            // Check val is present in each remaining array 
            i = arrayCount;
            while (!missing && i--) {
                if ( !arrayContains(arrays[i], val) ) {
                    missing = true;
                }
            }
            if (!missing) {
                intersection.push(val);
            }
        }
    }
    return intersection;
}

arrayIntersection( [1, 2, 3, "a"], [1, "a", 2], ["a", 1] ); // Gives [1, "a"]; 

建立在Anon的优秀答案之上,这个返回两个或更多数组的交集。

function arrayIntersect(arrayOfArrays)
{        
    var arrayCopy = arrayOfArrays.slice(),
        baseArray = arrayCopy.pop();

    return baseArray.filter(function(item) {
        return arrayCopy.every(function(itemList) {
            return itemList.indexOf(item) !== -1;
        });
    });
}

我会尽力为我做出最适合的事情:

if (!Array.prototype.intersect){
Array.prototype.intersect = function (arr1) {

    var r = [], o = {}, l = this.length, i, v;
    for (i = 0; i < l; i++) {
        o[this[i]] = true;
    }
    l = arr1.length;
    for (i = 0; i < l; i++) {
        v = arr1[i];
        if (v in o) {
            r.push(v);
        }
    }
    return r;
};
}

我将tarulen的答案扩展到了任何数组。 它也应该使用非整数值。

function intersect() { 
    const last = arguments.length - 1;
    var seen={};
    var result=[];
    for (var i = 0; i < last; i++)   {
        for (var j = 0; j < arguments[i].length; j++)  {
            if (seen[arguments[i][j]])  {
                seen[arguments[i][j]] += 1;
            }
            else if (!i)    {
                seen[arguments[i][j]] = 1;
            }
        }
    }
    for (var i = 0; i < arguments[last].length; i++) {
        if ( seen[arguments[last][i]] === last)
            result.push(arguments[last][i]);
        }
    return result;
}

破坏性似乎最简单,特别是如果我们可以假设输入是排序的:

/* destructively finds the intersection of 
 * two arrays in a simple fashion.  
 *
 * PARAMS
 *  a - first array, must already be sorted
 *  b - second array, must already be sorted
 *
 * NOTES
 *  State of input arrays is undefined when
 *  the function returns.  They should be 
 *  (prolly) be dumped.
 *
 *  Should have O(n) operations, where n is 
 *    n = MIN(a.length, b.length)
 */
function intersection_destructive(a, b)
{
  var result = [];
  while( a.length > 0 && b.length > 0 )
  {  
     if      (a[0] < b[0] ){ a.shift(); }
     else if (a[0] > b[0] ){ b.shift(); }
     else /* they're equal */
     {
       result.push(a.shift());
       b.shift();
     }
  }

  return result;
}

无损必须是一个更复杂的头发,因为我们必须跟踪指数:

/* finds the intersection of 
 * two arrays in a simple fashion.  
 *
 * PARAMS
 *  a - first array, must already be sorted
 *  b - second array, must already be sorted
 *
 * NOTES
 *
 *  Should have O(n) operations, where n is 
 *    n = MIN(a.length(), b.length())
 */
function intersect_safe(a, b)
{
  var ai=0, bi=0;
  var result = [];

  while( ai < a.length && bi < b.length )
  {
     if      (a[ai] < b[bi] ){ ai++; }
     else if (a[ai] > b[bi] ){ bi++; }
     else /* they're equal */
     {
       result.push(a[ai]);
       ai++;
       bi++;
     }
  }

  return result;
}

这是我正在使用的一个非常天真的实现。 它是非破坏性的,也确保不会重复有效。

Array.prototype.contains = function(elem) {
    return(this.indexOf(elem) > -1);
};

Array.prototype.intersect = function( array ) {
    // this is naive--could use some optimization
    var result = [];
    for ( var i = 0; i < this.length; i++ ) {
        if ( array.contains(this[i]) && !result.contains(this[i]) )
            result.push( this[i] );
    }
    return result;
}

这里对最小的一个进行微调( filter / indexOf解决方案 ),即使用JavaScript对象为其中一个数组创建索引值,将其从O(N * M)降低到“可能”线性时间。 source1

function intersect(a, b) {
  var aa = {};
  a.forEach(function(v) { aa[v]=1; });
  return b.filter(function(v) { return v in aa; });
}

这不是最简单的解决方案(它比filter + indexOf更多的代码),也不是最快的(可能比constantct_safe intersect_safe()更慢),但似乎是一个非常好的平衡。 这是非常简单的一面,同时提供良好的性能,并且不需要预先分类的输入。


通过使用.pop而不是.shift,可以改进@ atk实现排序的基元数组的性能。

function intersect(array1, array2) {
   var result = [];
   // Don't destroy the original arrays
   var a = array1.slice(0);
   var b = array2.slice(0);
   var aLast = a.length - 1;
   var bLast = b.length - 1;
   while (aLast >= 0 && bLast >= 0) {
      if (a[aLast] > b[bLast] ) {
         a.pop();
         aLast--;
      } else if (a[aLast] < b[bLast] ){
         b.pop();
         bLast--;
      } else /* they're equal */ {
         result.push(a.pop());
         b.pop();
         aLast--;
         bLast--;
      }
   }
   return result;
}

我使用jsPerf创建了一个基准: http://bit.ly/P9FrZK ://bit.ly/P9FrZK。 使用.pop的速度大约快三倍。


'use strict'

// Example 1
function intersection(a1, a2) {
    return a1.filter(x => a2.indexOf(x) > -1)
}

// Example 2 (prototype function)
Array.prototype.intersection = function(arr) {
    return this.filter(x => arr.indexOf(x) > -1)
} 

const a1 = [1, 2, 3]
const a2 = [2, 3, 4, 5]

console.log(intersection(a1, a2))
console.log(a1.intersection(a2))


function getIntersection(arr1, arr2){
    var result = [];
    arr1.forEach(function(elem){
        arr2.forEach(function(elem2){
            if(elem === elem2){
                result.push(elem);
            }
        });
    });
    return result;
}

getIntersection([1,2,3], [2,3,4,5]); // [ 2, 3 ]

function intersection(A,B){
var result = new Array();
for (i=0; i<A.length; i++) {
    for (j=0; j<B.length; j++) {
        if (A[i] == B[j] && $.inArray(A[i],result) == -1) {
            result.push(A[i]);
        }
    }
}
return result;
}




intersection