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

Question

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

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

问题陈述:

找到上一个数组中currentArray中缺少的元素.

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-loop风格:

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

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;

}