Dadas estas matrices, quiero verificar si "secuencia" es una subsecuencia de "matriz", lo que significa que todos los números existen en la matriz original y en el mismo orden:
array = [5, 1, 22, 25, 6, -1, 8, 10]; sequence = [1, 6, -1, 10];No estoy seguro de por qué mi código no funciona.
function isValidSubsequence(array, sequence) { let seqIdx = 0; let arrId = 0; for (const value of sequence ){ if (seqIdx === sequence.length) break; if (array[arrId] === value) { seqIdx++; arrId++; } } return seqIdx === sequence.length }Su solución no funciona porque nunca pasa de la primera entrada en array . Nunca incrementa ninguno de sus índices a menos que el valor de sequence coincida con array[arrId] .
Usaría una combinación de Array.prototype.indexOf() y Array.prototype.slice() para crear una ventana de array cada vez más pequeña mientras busca. Si alguna vez llega a una iteración de sequence que no se puede encontrar, sabe que falla la prueba
function isValidSubsequence(array, sequence) { let slice = array.slice(); // start with a shallow copy for (const value of sequence) { let index = slice.indexOf(value); // find the next sequence value if (index === -1) { return false; // not found, return false immediately } slice = slice.slice(index); // shrink the window } return true; } const array = [5, 1, 22, 25, 6, -1, 8, 10]; const sequence = [1, 6, -1, 10]; console.log("valid sub-sequence:", isValidSubsequence(array, sequence)) console.log("out of order:", isValidSubsequence(array, [25, 22])) console.log("unknown elements:", isValidSubsequence(array, [5, 11]))Quitar arrIdx .
En un bucle for...of , el índice de la array no es necesario en este caso, ya que el value progresa en cada iteración.
Elimine la primera declaración de control de flujo.
if (seqIdx === sequence.length) break;No hay necesidad de interrumpir el bucle. El valor booleano devuelto fuera del bucle es suficiente.
Cambie la segunda declaración de control de flujo para monitorear la sequence[seqIdx] no la array
if (sequence[seqIdx] === value) { seqIdx++; } La clave de este algoritmo es avanzar a través de la array un número a la vez (como es la norma), pero no la sequence . El contador, seqIdx , solo avanza en una coincidencia, por lo que, básicamente, si sequence termina antes o al final del ciclo, es una subsecuencia válida.
const arr = [5, 1, 22, 25, 6, -1, 8, 10]; const seq = [1, 6, -1, 10]; function isValidSubsequence(array, sequence) { let seqIdx = 0; for (const value of array) { if (sequence[seqIdx] === value) { seqIdx++; } } return seqIdx === sequence.length; }; console.log(isValidSubsequence(arr, seq));Puede lograrlo de una manera simple al encontrar el índice de los elementos de la matriz de secuencias de la matriz original y luego verificar si la matriz indexada está ordenada o no.
demostración:
const array = [5, 1, 22, 25, 6, -1, 8, 10]; const sequence = [1, 6, -1, 10]; // Find index of the elements from the original array. const indexArr = sequence.map((item) => array.indexOf(item)); // Now test if this indexed array is sorted or not to check if sequence array having same order as per the original array. function isSorted(arr) { var i = 0; var last = arr.length - 1; return (function check() { return (i >= last) || (arr[i] <= arr[++i] && check()); })(); } console.log(isSorted(indexArr))