通过比较 Javascript 中的 2 个数组来查找丢失的元素
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/9736804/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Find missing element by comparing 2 arrays in Javascript
提问by ninjagecko
For some reason I'm having some serious difficulty wrapping my mind around this problem. I need this JS function that accepts 2 arrays, compares the 2, and then returns a string of the missing element. E.g. Find the element that is missing in the currentArray that was there in the previous array.
出于某种原因，我在解决这个问题时遇到了一些严重的困难。我需要这个 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;
}
Thank in advance! I'm not asking for code, but even just a push in the right direction or a hint might help...
预先感谢！我不是在要求代码，但即使只是朝着正确的方向推动或提示也可能会有所帮助......
采纳答案by diolemo
This should work. You should also consider the case where the elements of the arrays are actually arrays too. The indexOf might not work as expected then.
这应该有效。您还应该考虑数组元素实际上也是数组的情况。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;
}
回答by ninjagecko
Problem statement:
问题陈述：
Find the element that is missing in the currentArray that was there in the previous array.
查找在上一个数组中存在的 currentArray 中缺少的元素。
previousArray.filter(function(x) { // return elements in previousArray matching...
return !currentArray.includes(x); // "this element doesn't exist in currentArray"
})
(This is as bad as writing two nested for-loops, i.e. O(N2) time. This can be made more efficient if necessary, by creating a temporary object out of currentArray, and using it as a hashtable for O(1) queries. For example:)
（这与编写两个嵌套的 for 循环一样糟糕，即 O(N 2) 时间。如有必要，可以通过从 中创建一个临时对象currentArray并将其用作 O(1) 查询的哈希表来提高效率。 例如：）
var inCurrent={}; currentArray.forEach(function(x){ inCurrent[x]=true });
So then we have a temporary lookup table, e.g.
那么我们有一个临时查找表，例如
previousArray = [1,2,3]
currentArray = [2,3];
inCurrent == {2:true, 3:true};
Then the function doesn't need to repeatedly search the currentArray every time which would be an O(N) substep; it can instantly check whether it's in currentArray in O(1) time. Since .filteris called N times, this results in an O(N) rather than O(N2) total time:
然后函数不需要每次都重复搜索 currentArray，这将是一个 O(N) 子步；它可以在 O(1) 时间内立即检查它是否在 currentArray 中。由于.filter被称为 N 次，这导致 O(N) 而不是 O(N 2) 总时间：
previousArray.filter(function(x) {
return !inCurrent[x]
})
Alternatively, here it is for-loop style:
或者，这里是 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}`)
Or just use modern data structures, which make the code much more obvious:
或者只是使用现代数据结构，这使代码更加明显：
var currentSet = new Set(currentArray);
return previousArray.filter(x => !currentSet.has(x))
回答by welldan97
Take a look at underscore differencefunction: http://documentcloud.github.com/underscore/#difference
看看下划线difference函数：http: //documentcloud.github.com/underscore/#difference
回答by andlrc
I know this is code but try to see the difference examples to understand the way:
我知道这是代码，但尝试查看差异示例以了解方式：
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);
Or using ECMAScript 5 indexOf:
或者使用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);
And with 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);
回答by Rajat Bansal
This is my approach(works for duplicate entries too):- //here 2nd argument is actually the current array
这是我的方法（也适用于重复条目）：- //这里的第二个参数实际上是当前数组
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
}
}
}
Logic is that i have created a blank array called hashtable. We iterate currentArray first and use the elements as index and values as counts starting from 1(this helps in situations when there are duplicate entries). Then we iterate through previousArray and look for indexes, if they match we reduce the value count by 1. If an element of 2nd array doesnt exist at all then our undefined check condition fires and we return it. If duplicates exists, they are decremented by 1 each time and when 0 is encountered, that elment is returned as missing element.
逻辑是我创建了一个名为 hashtable 的空白数组。我们首先迭代 currentArray 并使用元素作为索引和值作为从 1 开始的计数（这有助于在存在重复条目的情况下）。然后我们遍历 previousArray 并查找索引，如果它们匹配，我们将值计数减少 1。如果第二个数组的元素根本不存在，那么我们的未定义检查条件将触发并返回它。如果存在重复项，则每次递减 1，当遇到 0 时，该元素作为缺失元素返回。
