用javascript实现数组交叉的最简单、无库代码是什么?我想写

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

并获得

[2, 3]

当前回答

通过对数据的一些限制,您可以在线性时间内完成!

对于正整数:使用一个数组将值映射到“已见/未见”布尔值。

function intersectIntegers(array1,array2) { 
   var seen=[],
       result=[];
   for (var i = 0; i < array1.length; i++) {
     seen[array1[i]] = true;
   }
   for (var i = 0; i < array2.length; i++) {
     if ( seen[array2[i]])
        result.push(array2[i]);
   }
   return result;
}

对于对象也有类似的技术:取一个虚拟键,为array1中的每个元素设置为“true”,然后在array2的元素中寻找这个键。完事后收拾一下。

function intersectObjects(array1,array2) { 
   var result=[];
   var key="tmpKey_intersect"
   for (var i = 0; i < array1.length; i++) {
     array1[i][key] = true;
   }
   for (var i = 0; i < array2.length; i++) {
     if (array2[i][key])
        result.push(array2[i]);
   }
   for (var i = 0; i < array1.length; i++) {
     delete array1[i][key];
   }
   return result;
}

当然,你需要确保这个键之前没有出现过,否则你会破坏你的数据…

其他回答

通过使用.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创建了一个基准测试。使用。pop要快三倍。

使用一个数组创建一个Object,并循环遍历第二个数组以检查该值是否作为key存在。

function intersection(arr1, arr2) {
  var myObj = {};
  var myArr = [];
  for (var i = 0, len = arr1.length; i < len; i += 1) {
    if(myObj[arr1[i]]) {
      myObj[arr1[i]] += 1; 
    } else {
      myObj[arr1[i]] = 1;
    }
  }
  for (var j = 0, len = arr2.length; j < len; j += 1) {
    if(myObj[arr2[j]] && myArr.indexOf(arr2[j]) === -1) {
      myArr.push(arr2[j]);
    }
  }
  return myArr;
}

我写了一个相交函数,它甚至可以根据对象的特定属性来检测对象数组的交集。

例如,

if arr1 = [{id: 10}, {id: 20}]
and arr2 =  [{id: 20}, {id: 25}]

我们想要基于id属性的交集,那么输出应该是:

[{id: 20}]

因此,相同(注:ES6代码)的函数为:

const intersect = (arr1, arr2, accessors = [v => v, v => v]) => {
    const [fn1, fn2] = accessors;
    const set = new Set(arr2.map(v => fn2(v)));
    return arr1.filter(value => set.has(fn1(value)));
};

你可以这样调用这个函数:

intersect(arr1, arr2, [elem => elem.id, elem => elem.id])

还要注意:该函数查找交集时考虑到第一个数组是主数组,因此交集结果将是主数组的结果。

希望这有助于所有版本。

function diffArray(arr1, arr2) {
  var newArr = [];

  var large = arr1.length>=arr2.length?arr1:arr2;
  var small = JSON.stringify(large) == JSON.stringify(arr1)?arr2:arr1;
  for(var i=0;i<large.length;i++){
    var copyExists = false; 
    for(var j =0;j<small.length;j++){
      if(large[i]==small[j]){
        copyExists= true;
        break;
      }
    }
    if(!copyExists)
      {
        newArr.push(large[i]);
      }
  }

  for(var i=0;i<small.length;i++){
    var copyExists = false; 
    for(var j =0;j<large.length;j++){
      if(large[j]==small[i]){
        copyExists= true;
        break;
      }
    }
    if(!copyExists)
      {
        newArr.push(small[i]);
      }
  }


  return newArr;
}

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

/* 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;
}