[removed] efficiently compare two integer arrays

问题:

I have two integer arrays which contain numeric values. I want to look through both lists and check for commonality (or lack of) between the lists. I.e. I want to iterate through the array(s) and find those items which appear in both lists, while in a separate function I want to go through the arrays and find items which are in the first and not in the second.

The obvious way of doing this is nested for loops:

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
}

But given the lists could contain hundreds or thousands of records this is quite a bit of itteration and processor intensive. I was therefore wondering if there is a more efficient way of executing the above code? Not just the actual searching, but something more efficient than an Integer array as the container for the values, or just not using nested for loops to traverse and compare the content.

Any thoughts on more efficient or elegant solutions?

回答1:

Sort them first and duck-waddle through them in parallel.

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

回答2:

Everyone is overly complicating this. Here's a one liner:

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

回答3:

When using two nested loops the complexity will be O(n*n). Sorting both array can be done in complexity O(n log n).

AS Marcelo Cantos stated duck-waddle :) through both in paralell has complexity O(n) leading to an overall complexity of O(n log n) + O(n) which is O (n log n).

回答4:

I think I have solution with efficiency of O(N) (no sort needed), here it is:

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

The function will return new array with the items that exist in both arrays, and will assign global array with all items existing in first array that do not exist in second array.

This code is relying on the fact both arrays hold only integer numbers.

Usage example:

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

Tested with arrays having 100,000 items: less than one second. Tested with arrays having 200,000 items each: less than 2 seconds.

回答5:

Another possibility could be order those arrays while you create them. I am not sure if you can do that. But if you can, it will increase a bit the complextity of adding an element to the array (O(log n) instead of O(1)) but it will decrease the complexity of your comparison algorithm to O(n)

回答6:

Sort both arrays, than loop just once and compare:

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

This is not tested so if something is wrong please let me know.
Anyway this should set you to the right direction since it's O(N) at best and O(M) at worst if comparedArray.length > arrayToCompareTo.length, it's much more efficient than O(N^2). Note that the sorting takes O(N log N).