6

Например, есть 2 массива:

var days      = ["Понедельник", "Вторник", "Среда", "Четверг", 
    "Пятница", "Суббота", "Воскресенье"];
var work_days = ["Понедельник", "Вторник", "Среда", "Четверг", 
    "Пятница", "Рабочие дни"];

Как их сравнить и вывести результат:

"Суббота", "Воскресенье", "Рабочие дни"
7
  • 1
    @Sergiks ну можно и не за квадрат решение сделать, хотя бы за n log n. А лучше за n.
    – pavel
    10 июл 2016 в 10:57
  • 1
    @pavel массивы не отсортированы, как можно сделать за n? В частном случае, если предположить ограниченный набор возможных значений, задача становится совсем простой. Но этого в вопросе пока нет.
    – Sergiks
    10 июл 2016 в 11:01
  • 1
    @Sergiks хеш сет.
    – pavel
    10 июл 2016 в 11:13
  • 1
    вычисление одного MD5 хэша потребует, вероятно, больше операций, чем O(n^2) по массивам из примера )
    – Sergiks
    10 июл 2016 в 11:17
  • 1
    Ну мы же не звери md5 хеш делать) есть и проще, банальный полиномиальный хеш к примеру.
    – pavel
    10 июл 2016 в 11:22

4 ответа 4

5

Можно примерно так:

var days      = ["Понедельник", "Вторник", "Среда", "Четверг", 
    "Пятница", "Суббота", "Воскресенье"];
var work_days = ["Понедельник", "Вторник", "Среда", "Четверг", 
    "Пятница", "Рабочие дни"];

document.body.innerText = JSON.stringify( diff(days, work_days));

function diff( a, b) {
  var diff = a.filter((e)=>!~b.indexOf(e));
  return diff.concat(b.filter((e)=>!~a.indexOf(e)));
}

В функцию сравнения diff() передаём оба массива. Там с помощью метода .filter(), сначала отбираются те элементы a, которых нет в b. А затем к полученным добавляются наоборот – те из b, которых нет в a.

Использованы методы: склейка массивов .concat(), фильтр массива .filter()

4
  • какая сложность этого решения ?
    – ampawd
    10 июл 2016 в 17:40
  • @ampawd ужасная, O(n^2)
    – Sergiks
    10 июл 2016 в 18:09
  • @ampawd расскажите про решение O(n), считая, что нет повторов (хотя не всё ли равно?)
    – Sergiks
    10 июл 2016 в 21:15
  • 1
    заводятся два объекта Map ключи которых соотв. это элементы массивов, а значения true. далее проходами по исходным массивам идёт проверка на отсутсвие элементов первого во втором, потом ещё одним проходом по второму массиву та же проверка отсутвия второго массива в первом, а элементы прошедшие этот тест и будут разницей двух массивов - тоесть выходит 4 последовательных прохода циклами, что даёт итоговую сложность если быть совсем точным O(max(n, m)) где n и m размеры, а линейная зависивость обеспечивается за константной работы метода Map.prototype.has который будет проверять отсутсвие
    – ampawd
    10 июл 2016 в 23:08
2

Можно подготовить один из массивов и собрать из него объект, с помощью функции reduce, это позволит избавиться от indexOf

var days = ["Понедельник", "Вторник", "Среда", "Четверг",
  "Пятница", "Суббота", "Воскресенье"
];
var work_days = ["Понедельник", "Вторник", "Среда", "Четверг",
  "Пятница", "Рабочие дни"
];

document.body.innerText = JSON.stringify(diff(days, work_days));

function diff(a, b) {
  var m = days.reduce(function(a, d) {
    a[d] = 1;
    return a;
  }, {});
  var r = work_days.reduce(function(acc, el) {
    delete acc.rest[el];
    if (!acc.m[el]) acc.result.push(el);
    return acc;
  }, {
    m: m,
    result: [],
    rest: Object.assign({}, m)
  });
  return r.result.concat(Object.keys(r.rest));
}

2

Операция известная и реализована в куче библиотек. Один из вариантов — lodash.xor:

var days = ["Понедельник", "Вторник", "Среда", "Четверг", "Пятница", "Суббота", "Воскресенье"];
var work_days = ["Понедельник", "Вторник", "Среда", "Четверг", "Пятница", "Рабочие дни"];

var result = _.xor(days, work_days);
alert(result);
<script src="https://gitcdn.xyz/repo/lodash/lodash/4.13.1/dist/lodash.js"></script>

0

решение за O(n) по времени и O(n) по памяти и требующее не повторящихся элементов в массивах.

var days      = ["Понедельник", "Вторник", "Среда", "Четверг", 
    "Пятница", "Суббота", "Воскресенье"];
var workDays = ["Понедельник", "Вторник", "Среда", "Четверг", 
    "Пятница", "Рабочие дни"];

var diff = [];
var daysAsKeys = new Map();  // need ES6
days.forEach(function(day) {
  daysAsKeys.set(day, true);
});

var workDaysAsKeys = new Map();
workDays.forEach(function(workDay) {
  workDaysAsKeys.set(workDay, true);
});    

days.forEach(function(day) {
  if (!workDaysAsKeys.has(day))
    diff.push(day);
});

workDays.forEach(function(workDay) {
  if (!daysAsKeys.has(workDay))
    diff.push(workDay);
});

alert(diff)

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.