查找數組不工作的交集？

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/