在Javascript中比较两个数组以找到缺失元素

Question

因为某些原因，我对这个问题感到非常困惑。我需要一个接受两个数组并比较它们的JS函数，然后返回缺失元素的字符串。例如，在当前数组中查找之前存在的元素。

function findDeselectedItem(CurrentArray, PreviousArray){

var CurrentArrSize = CurrentArray.length;
var PrevousArrSize = PreviousArray.length;

// Then my brain gives up on me...
// I assume you have to use for-loops, but how do you compare them??

return missingElement;

}

提前感谢！我不是在请求代码，但是即使只是指导方向或提示，也可能会有所帮助...

- user818700

---

你需要将数组A的每个元素与数组B的每个元素进行比较。但是，如果你知道正在比较哪种类型的值，有一些方法可以加快这个过程。 - Felix Kling

Answer 1

问题陈述：

查找当前数组中缺失的在先前数组中存在的元素。

previousArray.filter(function(x) {  // return elements in previousArray matching...
    return !currentArray.includes(x);  // "this element doesn't exist in currentArray"
})

这种写法和嵌套两个for循环一样低效，即O(N²)时间复杂度*。如果需要更高效的写法，可以将currentArray创建为临时对象，并将其用作哈希表以实现O(1)查询。例如：

var inCurrent={}; currentArray.forEach(function(x){ inCurrent[x]=true });

那么，我们现在有一个临时查找表，例如：

previousArray = [1,2,3]
currentArray = [2,3];
inCurrent == {2:true, 3:true};

这样，函数就不需要每次都搜索currentArray，因为这将是一个O(N)的子步骤；它可以在O(1)时间内立即检查是否在currentArray中。由于.filter被调用了N次，这导致总时间复杂度为O(N)，而不是O(N²)：

previousArray.filter(function(x) {
    return !inCurrent[x]
})

或者，这是for循环的写法：

var inCurrent = {};
var removedElements = []
for(let x of currentArray)
    inCurrent[x] = true;
for(let x of previousArray)
    if(!inCurrent[x])
        removedElements.push(x)
        //break; // alternatively just break if exactly one missing element
console.log(`the missing elements are ${removedElements}`)

或者使用现代数据结构，使代码更加明显：

var currentSet = new Set(currentArray);
return previousArray.filter(x => !currentSet.has(x))

*(附注：或者在更一般的情况下，如此处所示，在取消选择超过1个元素的情况下，时间复杂度为O(M*N))

- ninjagecko

---

这是一个很棒的答案，一定要喜欢函数式编程。但是还需要更多的工作才能在非JS1.6浏览器中使其正常工作。幸运的是，Mozilla已经在兼容性部分为我们完成了这项工作：indexOf 和 filter。 - Hemlock

很奇怪，虽然这个答案是最好的，但我通过在检查元素 === -1 时返回它来找到了缺失的元素，而不是 !== -1： 在 ES6 中：previousArray.filter(prev => currentArray.indexOf(prev) === -1 - Jeanmichel Cote

@JeanmichelCote：啊，糟糕，我很惊讶四年来没有人发现这个问题...我误读了问题，认为元素缺失在错误的数组中。已编辑。 - ninjagecko

Answer 2

这应该可以工作。您还应考虑数组元素实际上也是数组的情况。此时，indexOf可能无法按预期工作。

function findDeselectedItem(CurrentArray, PreviousArray) {

   var CurrentArrSize = CurrentArray.length;
   var PreviousArrSize = PreviousArray.length;

   // loop through previous array
   for(var j = 0; j < PreviousArrSize; j++) {

      // look for same thing in new array
      if (CurrentArray.indexOf(PreviousArray[j]) == -1)
         return PreviousArray[j];

   }

   return null;

}

- diolemo

---

当我们有重复的条目时，比如previousArray=[5,5,7,7]和currentArray=[5,7,7]，它就无法工作了..然后返回null。 - Rajat Bansal

Answer 3

看一看underscore的difference函数: http://documentcloud.github.com/underscore/#difference

- welldan97

---

哇，太棒了，但它返回的是什么？一个数组还是一个单独的字符串变量？ - user818700

@DeanGrobler: => [1, 3, 4] 看起来像是一个数组。为什么你要一个字符串呢？反正你可以很容易地将一个数组转换成字符串。 - Felix Kling

@Felix Kling - 听起来是对的，只是想确认一下。谢谢 :-) - user818700

它返回一个数组。如果你只有一个缺失的元素，你可能想使用_.difference(CurrentArray,PreviousArray)[0]。附：underscore是一个很棒的库。我在几乎每个项目中都使用它。试试吧。 - welldan97

名称已更改为 lodash，您可以在此处找到它：https://lodash.com/docs/4.17.15#differenceBy。非常适用于对象数组。 - Matthis Kohli

Answer 4

我知道这是代码，但尝试看不同的示例来理解方式：

var current = [1, 2, 3, 4],
    prev = [1, 2, 4],
    isMatch = false,
    missing = null;

var i = 0, y = 0,
    lenC = current.length,
    lenP = prev.length;

for ( ; i < lenC; i++ ) {
    isMatch = false;
    for ( y = 0; y < lenP; y++ ) {
        if (current[i] == prev[y]) isMatch = true;
    }
    if ( !isMatch ) missing = current[i]; // Current[i] isn't in prev
}

alert(missing);

---

或者使用ECMAScript 5 indexOf：

var current = [1, 2, 3, 4],
    prev = [1, 2, 4],
    missing = null;

var i = 0,
    lenC = current.length;

for ( ; i < lenC; i++ ) {
    if ( prev.indexOf(current[i]) == -1 ) missing = current[i]; // Current[i] isn't in prev
}

alert(missing);

使用while循环

var current = [1, 2, 3, 4],
    prev = [1, 2, 4],
    missing = null,
    i = current.length;

while(i) {
    missing = ( ~prev.indexOf(current[--i]) ) ? missing : current[i];
}

alert(missing);

- Andreas Louv

---

使用这种方法，我们无法获取所有缺失的元素。 - Ravi Sharma

Answer 5

这是我的方法（适用于重复条目）： //这里第二个参数实际上是当前数组

function(previousArray, currentArray) {
    var hashtable=[]; 

    //store occurances of elements in 2nd array in hashtable
    for(var i in currentArray){
        if(hashtable[currentArray[i]]){
            hashtable[currentArray[i]]+=1; //add 1 for duplicate letters
        }else{
            hashtable[currentArray[i]]=1; //if not present in hashtable assign 1
        }
    }
    for(var i in previousArray){
            if(hashtable[previousArray[i]]===0 || hashtable[previousArray[i]] === undefined){ //if entry is 0 or undefined(means element not present)
                return previousArray[i]; //returning the missing element
            }
    else{
             hashtable[previousArray[i]]-=1; //reduce count by 1
        }

    }
}

逻辑是我创建了一个名为hashtable的空数组。我们首先迭代currentArray，并使用元素作为索引，值作为计数从1开始（这有助于处理重复条目的情况）。然后，我们遍历previousArray并查找索引，如果它们匹配，则将值计数减少1。如果第二个数组的元素根本不存在，则我们的未定义检查条件触发并返回它。如果存在重复项，则每次将其减少1，当遇到0时，该元素将作为缺失元素返回。

- Rajat Bansal