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：有效地比较两个整数数组

回答

相关问题