Сравнение двух массивов в JavaScript - Возврат различий
Принятие мы имеем:
array1 = ['A', 'B', 'C', 'D', 'E']; array2 = ['C', 'E'];
Есть ли доказанное и быстрое решение сравнить два массива друг с другом, возвращая один массив без значений, появляющихся в обоих массивах (C и E сюда). Так:
array3 = ['A', 'B', 'D']
должен быть вывод решения. (jQuery может быть включен),
спасибо.
3 ответа
Это установленная разница. Простая реализация:
jQuery.grep(array1, function(el)
{
return jQuery.inArray(el, array2) == -1;
});
Это O (m * n), где это размеры массивов. Вы можете сделать это за O (m + n), но вам нужно использовать какой-то хэш-набор. Вы можете использовать объект JavaScript как простой хэш-набор для строк. Для относительно небольших массивов все вышеперечисленное подойдет.
Я принял решение Мэтьюза, но не хочу игнорировать другое, более быстрое решение, которое я только что нашел.
var list1 = [1, 2, 3, 4, 5, 6];
var list2 = ['a', 'b', 'c', 3, 'd', 'e'];
var lookup = {};
for (var j in list2) {
lookup[list2[j]] = list2[j];
}
for (var i in list1) {
if (typeof lookup[list1[i]] != 'undefined') {
alert('found ' + list1[i] + ' in both lists');
break;
}
}
проверенное быстрое решение, о котором я знаю, - это двоичный поиск, который вы можете использовать после сортировки одного из массивов. поэтому решение требует времени, которое зависит от алгоритма сортировки. но не меньше log (N).