通过比较 Javascript 中的 2 个数组来查找缺失元素

Question

出于某种原因，我在思考这个问题时遇到了一些严重的困难。我需要这个 JS 函数，它接受 2 个数组，比较这两个数组，然后返回缺失元素的字符串。例如。查找前一个数组中当前数组中缺少的元素。

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;

}

提前致谢！我不是要求代码，但即使只是朝正确的方向推动或提示也可能有所帮助......

Answer 1

12 年后......在 ES6 中，想要快速找到答案的人可以使用：

prevArray = .....;
newArray = .....;

function firstElemNotIn(curArray, prevArray) {
    /*
        returns the first element in currentArray that 
          is not in also in previousArray, 
          or undefined if no such element exists
        
        We declare two elements are equal here if they are === or both NaN.
        See https://developer.mozilla.org/en-US/docs/Web/JavaScript/Equality_comparisons_and_sameness#comparing_equality_methods
    */
    
    let prevSet = new Set(prevArray);
    return curArray.find(x=> !prevSet.has(x));
}

（这会执行 O(n) 过程以从数组中初始化

new Set

，然后在

.find

内的每个元素在 O(1) 时间内查询该 Set（因此，如果到达末尾，则最坏情况为 O(n)） newArray）。如果您在重复更新

previousArray

时重复执行此操作，您将需要使用不同的或自定义的数据结构。）

请注意，在此类问题中，无论使用哪种语言，都必须特别小心地注意使用的是哪种等式，否则您可能会遇到微妙的错误（

[1,2]!=[1,2]

、NaN！==NaN 等） .

---

[ 原文如下，使用 2012 年存在的 javascript，除了一些可读性编辑... ]

---

问题陈述：

查找前一个数组中当前数组中缺少的元素。

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 = {};
for(let x of currentArray) {
    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) 时间）

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;

}

Answer 3

看下划线

difference

函数：http://documentcloud.github.com/underscore/#difference

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

还有一会儿

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

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
        }

    }
}

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