查找数组不工作的交集？

Question

我有一个二维数组，每个维中有任意数量的元素，所以它是[m] [n]数组，但第二维长度（n）是可变的。

第二维中的每个元素都包含一个数字，并且在所有维中只会存在一个数字。

因此，例如，该阵列可以是：

[ 
    [ 
     126, 
     131, 
     138, 
     139, 
     140, 
     143 
    ], 
    [ 
     126, 
     201 
    ] 
] 

记住m可以> 2.

这里是我的代码：

var theArray = [ 
    [126, 131, 138, 139, 140, 143], 
    [126, 201] 
]; 

for(var i = 0; i < theArray.length; i++) // loop through each array of numbers 
{ 
    $.each(theArray[i], function(index, value) // loop through all of the numbers in this array 
    { 
     var nextArray = (i+1<theArray.length?theArray[i+1]:theArray[0]); 
     if($.inArray(value, nextArray) == -1) // if this number is not in the next array 
     { 
      console.log("removing index: " + index + ", value: " + value); 
      theArray[i].splice(index, 1); // remove the number from the array 
     } 
    }); 
} 
console.log(theArray); 

输出是这：

removing index: 1, value: 131 
removing index: 2, value: 139 
removing index: 3, value: 143 
removing index: 4, value: undefined 
removing index: 5, value: undefined 
removing index: 1, value: 201 

Array 
    [ 
     [ 
      126, 
      138, 
      140, 
     ], 
     [ 
      126 
     ] 
    ] 

的jsfiddle：http://jsfiddle.net/hDL8K/

正如你所看到的，它几乎作品，但它无法删除两个值。

我认为这可能与index在foreach循环中增加每个循环和数组的大小减少，因为元素被删除，但我不知道。

为什么这不起作用，我该如何解决？

Answer 1

Functional version with jQuery

var theArrays = [[126, 131, 138, 139, 140,143],[126, 201]],result = theArrays[0]; 

$.each(theArrays, function(index, currentArray) { 
    result = $.grep(result, function(currentElement) { 
     return currentArray.indexOf(currentElement) !== -1; 
    }); 
}); 

console.log(result); 

简单的JavaScript版本：

var theArrays = [[126, 131, 138, 139, 140,143],[126, 201]],result = theArrays[0]; 

for (var i = 1; i < theArrays.length; i += 1) { 
    for (var j = 0; j < result.length; j += 1) { 
     if (theArrays[i].indexOf(result[j]) === -1) { 
      result.splice(j, 1); 
      j -= 1; 
     } 
    } 
} 

console.log(result); 

输出

[ 126 ] 

如果数组太大，那么它能够更好地将它们转换为对象，然后找到路口。因为对于较大的数组，对象中的项目查找速度会快得多。

var theObjects = []; 
for (var i = 0; i < theArrays.length; i += 1) { 
    var tempObject = {}; 
    for (var j = 0; j < theArrays[i].length; j += 1) { 
     tempObject[theArrays[i][j]] = true; 
    } 
    theObjects.push(tempObject); 
} 

var intersection = theObjects[0], result = []; 
for (var i = 1; i < theArrays.length; i += 1) { 
    for (var key in intersection) { 
     if (theObjects[i].hasOwnProperty(key) === false) { 
      delete intersection[key]; 
     } 
    } 
} 

for (var key in intersection) { 
    result.push(parseInt(key)); 
} 

console.log(result); 

Answer 2

我希望你的问题源于数组长度在你从数组中移除项目时被修改的事实。而不是直接操作数组，你可以使用函数构造一个新的数组和你的结果。通常我发现这种方法可以帮助减少代码中的错误。从您现有的代码，它可能是这样的：

function intersect(theArray){ 
    var result = []; 
    for(var i = 0; i < theArray.length; i++){ 
     var row = []; 
     $.each(theArray[i], function(index, value){ 
      var nextArray = (i+1 < theArray.length 
          ?theArray[i+1]:theArray[0]); 
      if($.inArray(value, nextArray) != -1) { 
       row.push(theArray[i][index]);  
      } 
     }); 
     result.push(row);   
    } 
    return result; 
} 

Example Here。虽然这确实会产生一个包含交叉点的多维数组 - 您可能只需要它的第一个元素。

Answer 3

不知道解决方案中问题的确切位置，但..
在这里，你有一个解决方案

var theArray = [ 
    [126, 131, 138, 139, 140, 143], 
    [126, 201] 
]; 

//Finds intersection of 2 arrays, returns new array 
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; 
} 

for(var i = 0; i < theArray.length; i++){ // loop through each array of numbers  
    var nextIndex = (i+1) % theArray.length; 
    theArray[i] = intersect_safe(theArray[i], theArray[nextIndex]); 
} 
console.log(theArray); 

编辑：如果你想找到交集不对矫正原有的阵列，仅仅通过改变代码的最后一行：

var intersection = theArray[0] || []; 
for(var i = 0; i < theArray.length; i++){ 
    intersection = intersect_safe(intersection, theArray[i]); 
} 
console.log(intersection); 

输出：[126]

干杯，来自La Paz，Boli通过

Answer 4

我更新了你的方法一点点：

for(var i = 0; i < theArray.length; i++) // loop through each array of numbers 
{ 
    $.each(theArray[i], function(index, value) // loop through all of the numbers in this array 
    { 
     var nextArray = theArray[i + 1]; 

     if(nextArray !== undefined && $.inArray(value, nextArray) == 0) 
     { 
      console.log("removing index: " + index + ", value: " + value); 
      theArray[i].splice(index, 1); // remove the number from the array 
     } 

    }); 
} 

现在就来试试：http://jsfiddle.net/SabdielRivera/hDL8K/2/