JavaScript：高效比较两个整数数组

Question

我有两个包含数字值的整数数组。我想查看这两个列表之间共同性（或缺乏共同性）。也就是说，我想遍历数组并找到那些同时出现在两个列表中的项目，而在另一个函数中，我想遍历这些数组并找到第一个列表中存在但第二个列表中不存在的项目。

显然的方法是使用嵌套的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
}

但是，考虑到这些列表可能包含数百或数千条记录，这需要进行大量的迭代和处理器运算。

因此，我想知道是否有一种更有效的执行上述代码的方法？不仅是实际搜索，而且还有比整数数组更高效的存储值的容器，或者不使用嵌套的for循环来遍历和比较内容的其他解决方案。

你有更有效或更优雅的解决方案吗？

- LDJ

---

只是一个建议，如果您的浏览器支持WebWorker，请在其中运行该任务 - fcalderan

你需要保持顺序吗？数组是否已排序？数组中有大整数吗？ - Lauri

Answer 1

大家都把这个问题复杂化了，以下是一个简单的方法：

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

- Timothy Perez

---

这个回答怎么解决提问者的问题“我想遍历数组并找出在第一个数组中但不在第二个数组中的项”？我认为你过于简化了问题。 - trincot

这正是我来这里的原因，比较两者是否相等。谢谢！ - vzybilly

@Timothy 简单而精妙，对于小型列表非常有用。 - Skary

Answer 2

首先进行排序，然后并行地穿过它们。

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

- Marcelo Cantos

---

加1给duck-waddle：一个有趣且非常形象的术语。 - Arye Eidelman

Answer 3

当使用两个嵌套循环时，复杂度将为O(n*n)。 对两个数组进行排序的复杂度可以在O(n log n)内完成。

正如Marcelo Cantos所说的那样，同时进行并行处理的复杂度为O(n)，导致总体复杂度为O(n log n) + O(n)，即O(n log n)。

- Thariama

---

@Thariama：我的解决方案够好吗？如何改进它？我的算法感有点生疏。 - the_drow

@the_drow：你的解决方案已经足够好了，但是你没有考虑到第二个所需的功能（获取所有不不同的元素）。 - Thariama

@Thariama：已修复，谢谢。我的复杂度判断正确吗？我的方法对于大数组来说足够好吗？ - the_drow

这个程序的复杂度很好，正如我所描述的那样（不是O(N)，因为排序算法需要O(n log n)）。 - Thariama

@Thariama：Marcelo Cantos的解决方案更具备特色，这是否意味着它更好？ - the_drow

好的，我在你的代码中仍然发现了一个错误（一开始没有注意到）：如果你有两个包含[1,2,3,4,5,6,7]和[1,3,4,5,6,7,8]的数组，在循环中进行比较将导致错误的结果。 - Thariama

Answer 4

另一种可能是在创建数组时对它们进行排序。我不确定你是否可以这样做。但如果你可以，它会增加添加元素到数组的复杂度 (从 O(1) 到 O(log n))，但会将比较算法的复杂度降低到 O(n)

- Pau

Answer 5

将两个数组排序，然后只需要循环一次并进行比较：

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)。

- the_drow

Answer 6

我认为我有一个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);

测试了包含10万个项目的数组：不到1秒钟。 测试了每个包含20万个项目的数组：不到2秒钟。

- Shadow The Spring Wizard