Найти недостающий элемент, сравнив 2 массива в Javascript

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) подэтапом;он может мгновенно проверить, находится ли он в currentArray за O (1) раз.Поскольку .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))

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
        }

    }
}

Логика в том, что я создал пустой массив с именем hashtable. Сначала мы выполняем итерацию currentArray и используем элементы в качестве индекса, а значения в качестве счетчиков, начиная с 1 (это помогает в ситуациях, когда есть повторяющиеся записи). Затем мы выполняем итерацию по предыдущему массиву и ищем индексы, если они совпадают, мы уменьшаем количество значений на 1. Если элемент 2-го массива вообще не существует, то запускается наше неопределенное условие проверки, и мы его возвращаем. Если дубликаты существуют, они уменьшаются на 1 каждый раз, а при обнаружении 0 этот элемент возвращается как отсутствующий элемент.