Попытка решить симметричную разницу, используя Javascript
Я пытаюсь найти решение для симметричной разности, используя JavaScript, который решает следующие задачи:
- принимает неопределенное количество массивов в качестве аргументов
- сохраняет исходный порядок чисел в массивах
- не удаляет дубликаты чисел в одном массиве
- удаляет дубликаты, встречающиеся в массивах
Таким образом, например, если входной сигнал ([1, 1, 2, 6], [2, 3, 5], [2, 3, 4]), решение будет, [1, 1, 6, 5, 4].
Я пытаюсь решить эту проблему как вызов, поставленный онлайн-сообществом программистов. Точные инструкции о состоянии вызова,
Создайте функцию, которая принимает два или более массивов и возвращает массив симметричной разности предоставленных массивов.
Математический термин симметричная разность относится к элементам в двух наборах, которые находятся либо в первом, либо во втором наборе, но не в обоих.
Хотя мое решение ниже находит числа, уникальные для каждого массива, оно устраняет все числа, встречающиеся более одного раза, и не сохраняет порядок чисел.
Мой вопрос очень похож на тот, который задавался при поиске симметричных различий / уникальных элементов в нескольких массивах в javascript. Однако решение не сохраняет первоначальный порядок чисел и не сохраняет дубликаты уникальных чисел, встречающиеся в отдельных массивах.
function sym(args){
var arr = [];
var result = [];
var units;
var index = {};
for(var i in arguments){
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;
}
symsym([1, 1, 2, 6], [2, 3, 5], [2, 3, 4]); // => Desired answer: [1, 1, 6. 5. 4]
21 ответ
Вот версия, которая использует Set объект, чтобы сделать для более быстрого поиска. Вот основная логика:
- Он помещает каждый массив, переданный в качестве аргумента, в отдельный объект Set (для облегчения быстрого поиска).
- Затем он выполняет итерацию каждого переданного в массиве и сравнивает его с другими объектами Set (объектами, созданными не из итеративного массива).
- Если элемент не найден ни в одном из других наборов, он добавляется к результату.
Итак, начинается с первого массива [1, 1, 2, 6], поскольку 1 не найден ни в одном из других массивов, каждый из первых двух 1 значения добавляются к результату. затем 2 находится во втором наборе, поэтому он не добавляется к результату. затем 6 не найден ни в одном из двух других наборов, поэтому он добавляется к результату. Тот же процесс повторяется для второго массива [2, 3, 5] где 2 а также 3 встречаются в других наборах, но 5 это не так 5 добавляется к результату. И, для последнего массива, только 4 не найден в других наборах. Итак, окончательный результат [1,1,6,5,4],
Set объекты используются для удобства и производительности. Можно использовать .indexOf() искать их в каждом массиве, или можно сделать свой собственный поиск типа Set с простым объектом, если вы не хотите полагаться на объект Set. Также есть частичное заполнение для объекта Set, которое будет работать здесь в этом ответе.
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);
}Как и во всех проблемах, лучше всего начать с написания алгоритма:
Конкатенированные версии массивов, где каждый массив фильтруется, чтобы содержать те элементы, которые не содержит ни один массив, кроме текущего
Тогда просто запишите это в JS:
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
;
}
);
}
);
}
)
);
}
Не комментируемая версия, написанная более кратко с использованием ES6:
function sym(...arrays) {
return [].concat(arrays .
map((array, i) => array .
filter(elt => !arrays .
some((a, j) => i !== j && a.indexOf(elt) >= 0))));
}
Я столкнулся с этим вопросом в своем исследовании той же проблемы кодирования в 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-й параметр обратного вызова вместо именованного массива из-за цепочки методов.
Это было очень весело!
const exclude = (a, b) => a.filter(v => !b.includes(v))
const symDiff = (first, ...rest) => rest.reduce((acc, x) => [
...exclude(acc, x),
...exclude(x, acc)
], first)
/* - - - */
console.log(symDiff([1, 3], ['Saluton', 3])) // [1, 'Saluton']
console.log(symDiff([1, 3], [2, 3], [2, 8, 5])) // [1, 8, 5]Еще одно простое, но удобочитаемое решение:
/*
This filters arr1 and arr2 from elements which are in both arrays
and returns concatenated results from filtering.
*/
function symDiffArray(arr1, arr2) {
return arr1.filter(elem => !arr2.includes(elem))
.concat(arr2.filter(elem => !arr1.includes(elem)));
}
/*
Add and use this if you want to filter more than two arrays at a time.
*/
function symDiffArrays(...arrays) {
return arrays.reduce(symDiffArray, []);
}
console.log(symDiffArray([1, 3], ['Saluton', 3])); // [1, 'Saluton']
console.log(symDiffArrays([1, 3], [2, 3], [2, 8, 5])); // [1, 8, 5]Используемые функции: Array.prototype.filter () | Array.prototype.reduce () | Array.prototype.includes ()
function sym(arr1, arr2, ...rest) {
//creating a array which has unique numbers from both the arrays
const union = [...new Set([...arr1,...arr2])];
// finding the Symmetric Difference between those two arrays
const diff= union.filter((num)=>!(arr1.includes(num)&&arr2.includes(num)))
//if there are more than 2 arrays
if(rest.length){
// recurrsively call till rest become 0
// i.e. diff of 1,2 will be the first parameter so every recurrsive call will reduce // the arrays till diff between all of them are calculated.
return sym(diff, rest[0], ...rest.slice(1))
}
return diff
}
Создайте карту с подсчетом всех уникальных значений (по массивам). Затем объедините все массивы и отфильтруйте неуникальные значения, используя карту.
const symsym = (...args) => {
// create a Map from the unique value of each array
const m = args.reduce((r, a) => {
// get unique values of array, and add to Map
new Set(a).forEach((n) => r.set(n, (r.get(n) || 0) + 1));
return r;
}, new Map());
// combine all arrays
return [].concat(...args)
// remove all items that appear more than once in the map
.filter((n) => m.get(n) === 1);
};
console.log(symsym([1, 1, 2, 6], [2, 3, 5], [2, 3, 4])); // => Desired answer: [1, 1, 6, 5, 4]Эта функция удаляет дубликаты, потому что исходная концепция симметричной разницы действует над наборами. В этом примере функция работает с наборами следующим образом: ((A △ B) △ C) △ D ...
function sym(...args) {
return args.reduce((old, cur) => {
let oldSet = [...new Set(old)]
let curSet = [...new Set(cur)]
return [
...oldSet.filter(i => !curSet.includes(i)),
...curSet.filter(i => !oldSet.includes(i))
]
})
}
// Running> sym([1, 1, 2, 6], [2, 3, 5], [2, 3, 4])
console.log(sym([1, 1, 2, 6], [2, 3, 5], [2, 3, 4]))
// Return> [1, 6, 5, 2, 4]
Мое краткое решение. В конце я удалил дубликаты фильтром ().
function sym() {
var args = Array.prototype.slice.call(arguments);
var almost = args.reduce(function(a,b){
return b.filter(function(i) {return a.indexOf(i) < 0;})
.concat(a.filter(function(i){return b.indexOf(i)<0;}));
});
return almost.filter(function(el, pos){return almost.indexOf(el) == pos;});
}
sym([1, 1, 2, 5], [2, 2, 3, 5], [3, 4, 5, 5]);
//Result: [4,5,1]
Чистое решение для JavaScript.
function diff(arr1, arr2) {
var arr3= [];
for(var i = 0; i < arr1.length; i++ ){
var unique = true;
for(var j=0; j < arr2.length; j++){
if(arr1[i] == arr2[j]){
unique = false;
break;
}
}
if(unique){
arr3.push(arr1[i]);}
}
return arr3;
}
function symDiff(arr1, arr2){
return diff(arr1,arr2).concat(diff(arr2,arr1));
}
symDiff([1, "calf", 3, "piglet"], [7, "filly"])
//[1, "calf", 3, "piglet", 7, "filly"]
function sym(args) {
var initialArray = Array.prototype.slice.call(arguments);
var combinedTotalArray = initialArray.reduce(symDiff);
// Iterate each element in array, find values not present in other array and push values in combinedDualArray if value is not there already
// Repeat for the other array (change roles)
function symDiff(arrayOne, arrayTwo){
var combinedDualArray = [];
arrayOne.forEach(function(el, i){
if(!arrayTwo.includes(el) && !combinedDualArray.includes(el)){
combinedDualArray.push(el);
}
});
arrayTwo.forEach(function(el, i){
if(!arrayOne.includes(el) && !combinedDualArray.includes(el)){
combinedDualArray.push(el);
}
});
combinedDualArray.sort();
return combinedDualArray;
}
return combinedTotalArray;
}
console.log(sym([1, 1, 2, 5], [2, 2, 3, 5], [3, 4, 5, 5]));Это код 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]
Альтернатива: используйте поиск внутри карты вместо массива
function sym(...vs){
var has = {};
//flatten values
vs.reduce((a,b)=>a.concat(b)).
//if element does not exist add it (value==1)
//or mark it as multiply found value > 1
forEach(value=>{has[value] = (has[value]||0)+1});
return Object.keys(has).filter(x=>has[x]==1).map(x=>parseInt(x,10));
}
console.log(sym([1, 2, 3], [5, 2, 1, 4],[5,7], [5]));//[3,4,7])
Это работает для меня:
function sym() {
var args = [].slice.call(arguments);
var getSym = function(arr1, arr2) {
return arr1.filter(function(each, idx) {
return arr2.indexOf(each) === -1 && arr1.indexOf(each, idx + 1) === -1;
}).concat(arr2.filter(function(each, idx) {
return arr1.indexOf(each) === -1 && arr2.indexOf(each, idx + 1) === -1;
}));
};
var result = getSym(args[0], args[1]);
var len = args.length - 1, i = 2;
while (--len) {
result = [].concat(getSym(result, args[i]));
i++;
}
return result;
}
console.info(sym([1, 1, 2, 5], [2, 2, 3, 5], [6, 8], [7, 8], [9]));Вот решение
let a=[1, 1, 2, 6]
let b=[2, 3, 5];
let c= [2, 3, 4]
let result=[...a,...b].filter(item=>!(a.includes(item) && b.includes(item) ))
result=[...result,...c].filter(item=>!(b.includes(item) && c.includes(item) ))
console.log(result) //[1, 1, 6, 5, 4]
Эй, если кто-то заинтересован, это мое решение:
function sym (...args) {
let fileteredArgs = [];
let symDiff = [];
args.map(arrayEl =>
fileteredArgs.push(arrayEl.filter((el, key) =>
arrayEl.indexOf(el) === key
)
)
);
fileteredArgs.map(elArr => {
elArr.map(el => {
let index = symDiff.indexOf(el);
if (index === -1) {
symDiff.push(el);
} else {
symDiff.splice(index, 1);
}
});
});
return (symDiff);
}
console.log(sym([1, 2, 3, 3], [5, 2, 1, 4]));Ниже код отлично работал во всех сценариях. Попробуйте приведенный ниже код
function sym() {
var result = [];
for (var i = 0; i < arguments.length; i++) {
if (i == 0) {
var setA = arguments[i].filter((val) => !arguments[i + 1].includes(val));
var setB = arguments[i + 1].filter((val) => !arguments[i].includes(val));
result = [...setA, ...setB];
i = i + 1;
} else {
var setA = arguments[i].filter((val) => !result.includes(val));
var setB = result.filter((val) => !arguments[i].includes(val));
result = [...setA, ...setB];
}
}
return result.filter((c, index) => {
return result.indexOf(c) === index;
}).sort();
}
Мой код прошел все тесты на аналогичный вопрос на freecodecamp . Ниже приведен код для того же.
function sym(...args) {
const result = args.reduce((acc, curr, i) => {
if (curr.length > acc.length) {
const arr = curr.reduce((a, c, i) => {
if(a.includes(c)){
}
if (!acc.includes(c) && !a.includes(c)) {
a.push(c);
}
if (!curr.includes(acc[i]) && i < acc.length) {
a.push(acc[i])
}
return a;
}, []);
return [...arr];
} else {
const arr = acc.reduce((a, c, i) => {
if(a.includes(c)){
}
if (!curr.includes(c) && !a.includes(c)) {
a.push(c);
}
if (!acc.includes(curr[i]) && i < curr.length) {
a.push(curr[i])
}
return a;
}, []);
return [...arr]
}
});
let ans = new Set([...result])
return [...ans]
}
sym([1,2,3,3],[5, 2, 1, 4,5]);
Краткое решение с использованием
- Стрелочные функции
- Синтаксис распространения массива
- Фильтр массива
- Уменьшение массива
- Установленный
- Остальные параметры
- Неявный возврат
const symPair = (a, b) =>
[...a.filter(item => !b.includes(item)),
...b.filter(item => !a.includes(item))]
const sym = (...args) => [...new Set(args.reduce(symPair))]
Функция работает для двух входных массивов, а функция
sym работает для двух или более массивов, используя
symPair как редуктор.