function areSimilar(a, b){
return a.sort().join('') === b.sort().join('');
}
console.log(areSimilar([1, 2, 3], [1, 2, 3])); //true
console.log(areSimilar([1, 2, 3], [2, 1, 3])); //true
console.log(areSimilar([1, 2, 2], [2, 1, 1])); //false
Two arrays are called similar if one can be obtained from another by swapping at most one pair of elements in one of the arrays.Given two arrays a and b, check whether they are similar.Example
For a = [1, 2, 3] and b = [1, 2, 3], the output should be
areSimilar(a, b) = true.
The arrays are equal, no need to swap any elements.
For a = [1, 2, 3] and b = [2, 1, 3], the output should be
areSimilar(a, b) = true.
We can obtain b from a by swapping 2 and 1 in b.
For a = [1, 2, 2] and b = [2, 1, 1], the output should be
areSimilar(a, b) = false.
4 Réponses :
Si je comprends bien, 2 matrices sont "similaires" s'ils contiennent les mêmes éléments et il n'y a pas plus de 2 différences (car si vous avez plus de 2 différences, vous ne pouvez pas simplement échanger 2 éléments et obtenir la même chose tableau).
Donc, je vais aller pour quelque chose comme ceci: p>
p>
function areSimilar(a, b) {
if (a.length != b.length) {
return false;
}
var differences = [];
for (var i = 0; i < a.length; ++i) {
if (a[i] !== b[i]) {
differences.push(i);
if (differences.length > 2) {
return false;
}
}
}
if (!differences.length) {
return true;
}
if (differences.length == 1) {
return false;
}
return Math.abs(differences[0] - differences[1]) == 1 && a[differences[0]] === b[differences[1]] && a[differences[1]] === b[differences[0]];
}
console.log(areSimilar([1, 2, 3], [1, 2, 3])); //true
console.log(areSimilar([1, 2, 3], [2, 1, 3])); //true
console.log(areSimilar([1, 2, 2], [2, 1, 1])); //false
console.log(areSimilar([2, 1, 1], [1, 1, 2])); //falseCet algorithme reviendra dans ce cas: A = [2, 1, 1]; B = [1, 1, 2]; Mais 2 opérations d'échange sont nécessaires dans A pour le rendre égal à B.
Attendez ? Vous permettez d'échanger uniquement des éléments voisins? Il pourrait être important de le dire dans la question
Voir les commentaires Après la question de l'OPS: échangeez au plus une paire d'éléments
J'ai corrigé la fonction
@ dev101: Je ne pense pas que "swap deux éléments" signifie "swaps deux adjacents éléments", mais vous devriez peut-être demander à OP de clarifier.
Vous avez toujours besoin de 2 permutations pour obtenir [2,1,1] de [1,1,2] - correct?
Non. Vous venez d'échanger l'index 0 avec index 2. C'est une permutation.
A [0] = 2, B [2] = 2. Comment osciller 2 avec 2 (valeurs) atteindra-t-il une égalité?
Connaissez-vous la version ES6 de cette solution?
Il suffit de remplacer le var par un laisse et que vous avez une version ES6 compatible. Peut-être que vous pouvez remplacer la bouclette avec une foreach mais que vous comparez 2 tableaux, vous aurez un code désordonné.
ou: B [0] = 1, A [2] = 1, toujours pas de changement.
@ Dev101 Comme je le comprends, un échange d'échange de 2 valeurs. Donc Swap (A [0], B [2]) est seulement 1 échange de swap.
Oui, sans doute à ce sujet.
@ Dev101: Échangez deux éléments dans l'un des tableaux . Ce n'est pas un échange (A [0], B [2]); C'est un échange (a [0], un [2]). Qui vous donne [1, 1, 2]
Y a-t-il une manière ES6? Et si nous utilisons SL () causera-t-il une grande complexité?
@ici cela a du sens, alors! Merci :)
Vous pouvez compter les éléments et prendre une carte p> code> pour garder une trace du compte.
function areSimilar(a, b) {
return a.length === b.length
&& b.every(
(m => v => m.get(v) && m.set(v, m.get(v) - 1))
(a.reduce((m, v) => m.set(v, (m.get(v) || 0) + 1), new Map()))
);
}
console.log(areSimilar([1, 2, 3], [1, 2, 3])); // true
console.log(areSimilar([1, 2, 3], [2, 1, 3])); // true
console.log(areSimilar([1, 2, 2], [2, 1, 1])); // false
C'est très joli mais, comme le code incorrect de l'OP, il vérifie seulement que les deux tableaux sont des permutations les unes des autres. Il reviendra véritables entrées données [1, 2, 3], [2, 3, 1] , qui ne peuvent pas être rendues identiques à un seul échange. Malgré tout, +1 pour un bel exemple de flèches de graisse.
Voici une version qui fonctionne dans O (n) heure (elle examine chaque position exactement une fois) et O (1) temps (pas de conteneurs temporaires; juste des scalaires):
p>
function areSimilar(a, b) {
/* Helper function:
* Compares a and b starting at index i, and returns the first
* index at which they differ. If there is no difference returns
* max(i, a.length)
*/
function nextDiff(i) {
while (i < a.length && a[i] == b[i]) ++i;
return i;
}
/* If lengths are different, obviously not similar */
if (a.length != b.length) return false;
diff1 = nextDiff(0);
/* If there is no difference, they're the same (and thus similar) */
if (diff1 >= a.length) return true;
/* Find the second difference */
diff2 = nextDiff(diff1 + 1);
/* Similar if there is a second difference
and a swap would produce equality
and there is no further difference.
*/
return diff2 < a.length
&& a[diff1] == b[diff2] && a[diff2] == b[diff1]
&& nextDiff(diff2 + 1) >= a.length;
}
console.log(areSimilar([1, 2, 3], [1, 2, 3])); //true (identical)
console.log(areSimilar([1, 2, 3], [2, 1, 3])); //true (single swap)
console.log(areSimilar([1, 2, 2], [2, 1, 1])); //false (not permutation)
console.log(areSimilar([2, 1, 1], [1, 1, 2])); //true (single swap, not adjacent)
console.log(areSimilar([1, 2, 3], [2, 3, 1])); //false (permutation, needs two swaps)Ceci est ma version de la réponse: elle reviendra FALSE au cas où 2 ou plusieurs opérations d'échange sont nécessaires.
L'algorithme est très simple et facile à comprendre, mais probablement pas optimal en termes de vitesse. P>
Les journaux de la console de débogage sont laissés à des fins éducatives. Vous pouvez donc voir comment cela fonctionne! :) p>
p>
function areSimilar(a, b) {
if (a.length != b.length) {
return false;
}
let differences = 0;
for (let i=0; i < a.length; i++) {
// console.log('a[i] = ' + a[i]);
// console.log('b[i] = ' + b[i]);
if (a[i] !== b[i]) {
differences++;
}
}
// console.log('differences: ' + differences);
// trivial case: arrays are identical
if (differences == 0) {
return true;
}
// we know that in this case no swap combination can return a == b
if (differences == 1) {
return false;
}
// clone a array into c array
let c = a.slice(0);
// set comparison variables
let comparison = 0;
let matchFound = 0;
// only this case should be tested, because if difference is > 2 similarity fails according to initial condition
if (differences == 2) {
for (let j=0; j < a.length; j++) {
for (let k=0; k < a.length; k++) {
// re(set) temp variables
c = a.slice(0);
comparison = 0;
// console.log('a = ' + a);
// console.log('reset c = ' + c);
// console.log('reset comparison = ' + comparison);
if (j !== k) {
// swap array value pairs
[ c[j], c[k] ] = [ c[k], c[j] ];
// console.log('c[j' + j + '][k' + k + ']: ' + c);
// compare arrays
for (let n=0; n < c.length; n++) {
if (b[n] !== c[n]) {
// console.log('b[n] = ' + a[n]);
// console.log('c[n] = ' + c[n]);
comparison++;
// console.log('comparison [' + n + '] = ' + comparison);
}
}
if (comparison === 0) {
matchFound = 1;
break;
}
}
}
}
}
// evaluate final result
if (matchFound === 1) {
return true;
}
return false;
}
// TEST ARRAYS
var a = [1, 2, 2, 3, 4];
var b = [1, 2, 2, 4, 3];
// TEST FUNCTION
if (areSimilar(a, b)) {
console.log('a & b are similar!');
} else {
console.log('a & b are NOT similar!');
}
// OTHER 'COMMON' TESTS
console.log(areSimilar([1, 2, 3], [1, 2, 3])); //true (identical)
console.log(areSimilar([1, 2, 3], [2, 1, 3])); //true (single swap)
console.log(areSimilar([1, 2, 2], [2, 1, 1])); //false (not permutation)
console.log(areSimilar([2, 1, 1], [1, 1, 2])); //true (single swap, not adjacent)
console.log(areSimilar([1, 2, 3], [2, 3, 1])); //false (permutation, needs two swaps)
"Deux matrices sont appelées similaires si on peut être obtenu à partir d'une autre en échangeant à la plupart des éléments d'une paire d'éléments dans l'un des tableaux." Ce n'est pas ce que votre fonction
aresimilar Vérifications, sauf si votre fonction ne s'appelle jamais uniquement avec des tableaux à trois éléments ...? Par exemple, il retourneraittrue pour[1, 1, 2, 2] et[2, 2, 1, 1] mais obtenir De l'ancien à ce dernier nécessite deux swaps, pas seulement un.Il suffit de poster des commentaires similaires que T.j, votre version de tri ne ferait pas la question de la question. Cela ne donne que le vrai vrai / faux que par accident sur la base des exemples fournis.
geeksforgeeks.org/...
Si je comprends ce droit, mon idée est de trier les deux tableaux par des valeurs (ce n'est pas vraiment important par lequel «algorithme», ascendant, descendant, par des cordes ou de comparaison). Une fois triés, vous pouvez comparer chaque position correspondante (touches) et si vous trouvez plus d'une différence, le résultat devrait renvoyer false.
@ dev101
si je comprends ce droit , malheureusement, votre partie importante des questions ->échangeez au plus une paire d'éléments Le tri est très certainement rompre cette règle.Merci @keith, vient de réaliser que tout en codant!