Попытка решить симметричную разницу с помощью Javascript

Я пытаюсь вычислить функцию решения sym (args) {var arr = []; var result = []; var units; var index = {}; for (var i в аргументах) {units = arguments [i]; for (var j = 0; j <units.length; j ++) {arr.push (units [j]); }} arr.forEach (function (a) {if (! index [a]) {index [a] = 0;} index [a] ++;}); for (var l in index) {if (index [l] === 1) {result.push (+ l); }} return result; } симсим ([1, 1, 2, 6], [2, 3, 5], [2, 3, 4]); // => Желаемый ответ: [1, 1, 6. 5. 4] симметричная разница с использованием javascript, которая выполняет следующие задачи:

  • принимает неопределенное количество массивов в качестве аргументов
  • сохраняет исходный порядок чисел в массивах
  • не удаляет дубликаты чисел в одиночных массивах
  • удаляет дубликаты, возникающие в массивах

Таким образом, например, если входной сигнал (Set, [[1, 1, 2, 6], 1, 1], [2, 3, 6]), то решением будет [[2, 3, 5] , 2, 3, 5, 4].

Я пытаюсь решить это как вызов, заданный сообществом онлайн-кодирования. Точные инструкции состояния вызова,

Создайте функцию, которая принимает два или более массива и возвращает массив симметричной разности предоставленных массивов.

Математический термин «симметричная разность» относится к элементам в двух пяти, которые находятся либо в первом, либо в втором 4, но не в обоих.

Хотя мое решение ниже находит числа, которые уникальны для каждого массива, он устраняет все числа, происходящие более одного раза, и не сохраняет порядок чисел.

Мой вопрос очень близок к тому, который задавался при поиске симметричных разностных / уникальных элементов в нескольких массивах в javascript . Однако решение не сохраняет исходный порядок чисел и не сохраняет дубликаты уникальных чисел, встречающихся в одиночных массивах.

[1,1,6,5,4]

javascript,arrays,symmetric-difference,

10

Ответов: 14


10 принят

Вот версия, которая использует этот Setобъект для ускорения поиска. Вот основная логика:

  1. Он помещает каждый массив в качестве аргумента в отдельный объект Set (чтобы облегчить быстрый поиск).
  2. Затем он выполняет итерацию каждого переданного массива и сравнивает его с другими объектами Set (те, которые не сделаны из массива, который повторяется).
  3. Если элемент не найден ни в одном из других наборов, он добавляется к результату.

Итак, он начинается с первого массива [1, 1, 2, 6]. Так 1как не найдено ни в одном из других массивов, каждое из первых двух 1значений добавляется к результату. Затем он 2находится во втором наборе, поэтому он не добавляется к результату. Тогда 6он не найден ни в одном из двух других наборов, поэтому он добавляется к результату. Тот же процесс повторяется для второго массива, .indexOf()где 2и 3находятся в других наборах, но 5не так 5добавляется к результату. И для последнего массива только 4в других наборах не найдено. Итак, конечный результат function symDiff() { var sets = [], result = []; // make copy of arguments into an array var args = Array.prototype.slice.call(arguments, 0); // put each array into a set for easy lookup args.forEach(function(arr) { sets.push(new Set(arr)); }); // now see which elements in each array are unique // e.g. not contained in the other sets args.forEach(function(array, arrayIndex) { // iterate each item in the array array.forEach(function(item) { var found = false; // iterate each set (use a plain for loop so it's easier to break) for (var setIndex = 0; setIndex < sets.length; setIndex++) { // skip the set from our own array if (setIndex !== arrayIndex) { if (sets[setIndex].has(item)) { // if the set has this item found = true; break; } } } if (!found) { result.push(item); } }); }); return result; } var r = symDiff([1, 1, 2, 6], [2, 3, 5], [2, 3, 4]); log(r); function log(x) { var d = document.createElement("div"); d.textContent = JSON.stringify(x); document.body.appendChild(d); }.

Эти Setобъекты используются для удобства и производительности. Можно было бы использовать их Setдля поиска в каждом массиве, или вы могли бы сделать свой собственный поиск по типу с простым объектом, если бы не хотели полагаться на объект Set. Также есть частичный полипол для объекта Set, который будет работать здесь в этом ответе .

function symDiff() {
    var sets = [], result = [], LocalSet;
    if (typeof Set === "function") {
        try {
            // test to see if constructor supports iterable arg
            var temp = new Set([1,2,3]);
            if (temp.size === 3) {
                LocalSet = Set;
            }
        } catch(e) {}
    }
    if (!LocalSet) {
        // use teeny polyfill for Set
        LocalSet = function(arr) {
            this.has = function(item) {
                return arr.indexOf(item) !== -1;
            }
        }
    }
    // make copy of arguments into an array
    var args = Array.prototype.slice.call(arguments, 0);
    // put each array into a set for easy lookup
    args.forEach(function(arr) {
        sets.push(new LocalSet(arr));
    });
    // now see which elements in each array are unique 
    // e.g. not contained in the other sets
    args.forEach(function(array, arrayIndex) {
        // iterate each item in the array
        array.forEach(function(item) {
            var found = false;
            // iterate each set (use a plain for loop so it's easier to break)
            for (var setIndex = 0; setIndex < sets.length; setIndex++) {
                // skip the set from our own array
                if (setIndex !== arrayIndex) {
                    if (sets[setIndex].has(item)) {
                        // if the set has this item
                        found = true;
                        break;
                    }
                }
            }
            if (!found) {
                result.push(item);
            }
        });
    });
    return result;
}


var r = symDiff([1, 1, 2, 6], [2, 3, 5], [2, 3, 4]);
log(r);

function log(x) {
    var d = document.createElement("div");
    d.textContent = JSON.stringify(x);
    document.body.appendChild(d);
}

Одной из ключевых частей этого кода является то, как он сравнивает данный элемент с наборами из других массивов. Он просто выполняет итерацию по списку объектов Set, но пропускает объект Set, который имеет тот же индекс в массиве, что и повторяющийся массив. Это пропускает Set из этого массива, поэтому он ищет только элементы, которые существуют в других массивах. Это позволяет сохранить дубликаты, которые встречаются только в одном массиве.


Вот версия, которая использует Setобъект, если он присутствует, но добавляет замену для подростков, если нет (так это будет работать в более старых браузерах):

function sym() {
  var arrays = [].slice.apply(arguments);

  return [].concat.apply([],               // concatenate
    arrays.map(                            // versions of the arrays
      function(array, i) {                 // where each array
        return array.filter(               // is filtered to contain
          function(elt) {                  // those elements which
            return !arrays.some(           // no array
              function(a, j) {             // 
                return i !== j             // other than the current one
                  && a.indexOf(elt) >= 0   // contains
                ;
              }
            );
          }
        );
      }
    )
  );
}


16

Как и во всех проблемах, лучше всего начать писать алгоритм:

Объединяйте версии массивов, где каждый массив фильтруется, чтобы содержать те элементы, в которых нет массива, отличного от текущего.

Тогда просто напишите это в JS:

function sym(...arrays) {
  return [].concat(arrays . 
    map((array, i) => array . 
      filter(elt => !arrays . 
        some((a, j) => i !== j && a.indexOf(elt) >= 0))));
}

Некоммерческая версия, написанная более кратко с использованием ES6:

for

6

Я столкнулся с этим вопросом в своих исследованиях с тем же вопросом кодирования для FCC. Я смог решить эту проблему с помощью циклов forи whileпетель, но некоторые проблемы решались с использованием рекомендованных Array.reduce(). Изучив тон .reduceи другие методы массива, я решил поделиться своими решениями.

Это первый способ, которым я решил это, без использования .reduce.

function sym() {
  var arrays = [].slice.call(arguments);

  function diff(arr1, arr2) {
    var arr = [];

    arr1.forEach(function(v) {
      if ( !~arr2.indexOf(v) && !~arr.indexOf(v) ) {
        arr.push( v );
      }
    });

    arr2.forEach(function(v) {
      if ( !~arr1.indexOf(v) && !~arr.indexOf(v) ) {
        arr.push( v );
      }
    });
    return arr;
  }

  var result = diff(arrays.shift(), arrays.shift());

  while (arrays.length > 0) {
    result = diff(result, arrays.shift());
  }

  return result;
}

Изучив и пробовав различные комбинации методов, я придумал это, что я считаю довольно кратким и удобочитаемым.

function sym() {
  var arrays = [].slice.call(arguments);

  function diff(arr1, arr2) {
    return arr1.filter(function (v) {
      return !~arr2.indexOf(v);
    });
  }

  return arrays.reduce(function (accArr, curArr) { 
    return [].concat( diff(accArr, curArr), diff(curArr, accArr) )
    .filter(function (v, i, self) { return self.indexOf(v) === i; });
  });

}

Эта последняя .filterстрока, которая, как мне показалось, была довольно классной для дедуплирования массива. Я нашел его здесь , но изменил его, чтобы использовать третий параметр обратного вызова вместо именованного массива из-за цепочки методов.

Этот вызов был очень интересным!


3

Просто используйте код _.xor или копию lodash.


1

Это код JS с использованием функций более высокого порядка

    function sym(args) {
      var output;
      output = [].slice.apply(arguments).reduce(function(previous, current) {
        current.filter(function(value, index, self) { //for unique
          return self.indexOf(value) === index;
        }).map(function(element) { //pushing array
          var loc = previous.indexOf(element);
          a = [loc !== -1 ? previous.splice(loc, 1) : previous.push(element)];
        });
        return previous;
      }, []);
      document.write(output);
      return output;
    }

    sym([1, 2, 3], [5, 2, 1, 4]);

И он вернет результат как: [3,5,4]

JavaScript, массивы, симметричная-разностный,
Похожие вопросы