Javascript：有效地比較兩個整數數組

我有兩個包含數值的整型數組。我想查看兩個列表並檢查列表之間的共同性（或缺少）。即我想循環訪問數組並找到出現在這兩個列表中的項目，而在一個單獨的函數中，我想通過數組找到第一個項目，而不是第二個項目。Javascript：有效地比較兩個整數數組

這樣做的最顯而易見的方法是嵌套的for循環：

var containedInFirst = false; 
for (var primaryID = 0; primaryID < PrimaryArray.length; primaryID++) { 
     containedInFirst = false; 
     for (var secondaryID = 0; secondaryID < SecondaryArray.length; secondaryID++) { 
      if (PrimaryArray [primaryID] === SecondaryArray[secondaryID]) { 
       containedInFirst = true; 
       break; 
      } 
     } 

//Do some more stuff based on the value of containedInFirst here 
}

但考慮到列表可以包含的記錄成百上千，這是相當多的itteration和處理器密集型的。因此，我想知道是否有更高效的方式來執行上述代碼？不僅僅是實際的搜索，而是比Integer數組更有效的值作爲容器的值，或者不使用嵌套for循環遍歷和比較內容。

有關更高效或優雅解決方案的任何想法？

來源

2010-11-16 LDJ

只是一個建議，爲「優雅」的一部分=）運行任務的webworker如果你的瀏覽器支持他們 – 2010-11-16 11:57:41

你有維持秩序？數組是否已排序？你在數組中有大整數嗎？ – Lauri 2010-11-16 12:56:53

首先對它們進行排序，並將它們平行排列。

a.sort(); 
b.sort(); 

left = []; both = []; right = []; 
i = 0; j = 0; 
while (i < a.length && j < b.length) { 
    if (a[i] < b[j]) { 
     left.push(a[i]); 
     ++i; 
    } else if (b[j] < a[i]) { 
     right.push(b[j]); 
     ++j; 
    } else { 
     both.push(a[i]); 
     ++i; ++j; 
    } 
} 
while (i < a.length) { 
    left.push(a[i]); 
    ++i; 
} 
while (j < b.length) { 
    right.push(b[j]); 
    ++j; 
}

來源

2010-11-16 11:47:11

排序兩個數組，比循環只有一次，並比較：

function diff(arrayToCompareTo, comparedArray) 
{ 
    Sort(arrayToCompareTo); 
    Sort(comparedArray); 

    var difference = [], same = []; 
    for(var i = 0; i < arrayToCompareTo.length; ++i) 
    { 
    if (arrayToCompareTo[i] != comparedArray[i]) 
     difference.push(comparedArray[i]); 
    else 
     same.push(comparedArray[i]); 
    } 

    if (comparedArray.length > arrayToCompareTo.length) 
    for(var i = arrayToCompareTo.length; i < comparedArray.length; ++i) 
     difference.push(comparedArray[i]); 
}

這不是測試，因此，如果事情是錯了，請讓我知道。
無論如何，這應該設置你正確的方向，因爲它最好是O（N），而O（M）最差如果comparedArray.length > arrayToCompareTo.length，它比O（N^2）更有效率。請注意，排序需要O（N log N）。

來源

2010-11-16 11:52:21

當使用兩個嵌套循環時，複雜度將爲O（n * n）。對這兩個數組進行排序可以用複雜度O（n log n）來完成。

AS Marcelo Cantos指出duck-waddle :) 通過並行方式具有複雜度O（n）導致O（n log n）+ O（n）的總體複雜度爲O（n log n）。

來源

2010-11-16 11:52:34 Thariama

@Thariama：我的解決方案夠好嗎？如何改進？我的算法感覺有點生疏。 – 2010-11-16 11:55:50

@ the_drow：你的解決方案已經足夠好了，但是你不需要關心第二個功能（所有的元素都是不一樣的） – Thariama 2010-11-16 12:22:28

@Thariama：修正，謝謝。我對複雜性是否正確？我的方法對於大型數組足夠好嗎？ – 2010-11-16 13:20:09

我覺得我有O（N）的效率的解決方案（沒有那種需要），那就是：

var firstNotSecond; 
function CompareIntArrays(arr1, arr2) 
{ 
    firstNotSecond = new Array(); 

    var arr3 = new Array(); //appear in both 
    var arrTemp = new Array(); //used for firstNotSecond 
    var usedNumbers = new Array(); 

    for (var i = 0; i < arr1.length; i++) 
    { 
     var key = arr1[i]; 
     usedNumbers[key] = true; 
     arrTemp[key + ""] = true; 
    } 

    for (var i = 0; i < arr2.length; i++) 
    { 
     var key = arr2[i]; 
     if (usedNumbers[key]) 
     { 
      arr3[arr3.length] = key; 
      arrTemp[key] = false; 
     } 
    } 

    for (var key in arrTemp) 
     if (arrTemp[key]) 
      firstNotSecond[firstNotSecond.length] = parseInt(key); 

    return arr3; 
}

該函數將返回與存在於兩個數組項新的陣列，並會將全局數組分配給第一個數組中不存在的所有項目。

這段代碼依賴於這兩個數組只保留整數的事實。

用例：

alert(CompareIntArrays([15, 551, 25, 910, 11], [25, 11, 785, 880, 15])); 
alert(firstNotSecond);

測試與具有100,000個項目陣列：小於一秒。使用每個200,000個項目的陣列進行測試：小於2秒。

來源

2010-11-16 14:01:39

另一種可能性可能是在創建這些數組時創建它們。我不確定你是否可以這樣做。但是如果可以的話，它會增加一點元素到數組中的補充性（O（log n）而不是O（1）），但是它會將比較算法的複雜度降低到O（n）

來源

2010-11-16 14:02:01 Pau

每個人都過分複雜化。這裏是一個班輪：

var isEqual = (JSON.stringify(arr1.sort()) === JSON.stringify(arr2.sort()));

來源

2015-09-02 12:41:47

Javascript：有效地比較兩個整數數組

回答

相關問題