Estoy tratando de revertir una matriz en JS en el lugar (sin usar una matriz adicional). Estoy usando split-merge recursivamente (primero divido la matriz en dos mitades y luego reorganizo cada mitad por separado y luego combino los resultados de las dos disposiciones). el problema parece surgir si la longitud de la matriz es un número impar, en cuyo caso existirá una matriz que tiene un solo elemento y otra matriz que tiene dos elementos.
ejemplo :
reverseArrayInPlace([1, 5, 0, 4, 6]) debería funcionar así:
1- reverseArrayInPlace([1,5,0]) -> devuelve las siguientes llamadas
ahora las dos matrices de la primera llamada deben fusionarse e intercambiarse. El resultado debería ser [0,5,1]
2- invertirArrayInPlace([4, 6]) -> devuelve [6,4]
Ahora, el resultado de la llamada (1) y la llamada (2) debe fusionarse e intercambiarse (usando también concat); lo que hará que el resultado sea: [6,4,0,5,1].
Sé que hay otras formas más fáciles, pero quiero saber por qué mi código no devuelve el valor correcto.
let reverseArrayInPlace = ar => { let splitArray = arr => { if( arr.length === 1){ console.log('length = 1', arr); return arr; } else if(arr.length === 2){ console.log('length = 2', arr); let temp = arr[0]; arr[0] = arr[1]; arr[1] = temp; return arr; } else{ reverseArrayInPlace(arr); //reverseArrayInPlace (ar2); } } let mergeArray = (arr1, arr2) => { console.log("Swapping : ", arr1, arr2); console.log('Concated : ',arr2.concat(arr1)); if(arr1 === undefined) return arr2; else if(arr2 === undefined) return arr1; else return arr2.concat(arr1); } let half = Math.ceil(ar.length / 2); //console.log('half = ', half); ar1 = splitArray(ar.slice(0, half)); ar2 = splitArray(ar.slice(half)); //console.log(arr1, arr2); return mergeArray(ar1, ar2); } let ar = [1, 5, 0, 4, 6]; console.log(reverseArrayInPlace(ar));En su función de matriz dividida, pierde un return :
let splitArray = arr => { if( arr.length === 1){ console.log('length = 1', arr); return arr; } else if(arr.length === 2){ console.log('length = 2', arr); let temp = arr[0]; arr[0] = arr[1]; arr[1] = temp; return arr; } else{ ***RETURN*** reverseArrayInPlace(arr); //reverseArrayInPlace (ar2); } } Utilicé el depurador en el navegador de Chrome para ir paso a paso y noté que ar1 era nulo en su step 1- reverseArrayInPlace([1,5,0]) -> returns the below calls lo que el resultado contiene solo la segunda parte: el segundo invertido matriz [6,4]
La declaración de return que falta es el problema inicial, pero en términos más generales, este no es un verdadero algoritmo en el lugar, porque todavía reserva O (n) memoria auxiliar al crear nuevas matrices.
Para que un algoritmo esté en su lugar, no debe haber uso de memoria auxiliar O(n). En su lugar, haga también las splitArray y mergeArray inplace, de modo que en todo momento solo haya una matriz que esté siendo mutada.
Para que eso suceda, deberá pasar los índices de inicio/fin del subarreglo que será objeto de la operación de división/fusión.
También es más seguro incluir el caso de matriz vacía en el primer caso base de splitArray : así que use <= 1 en lugar de === 1 .
Aquí está su código alterado con esa idea:
let reverseArrayInPlace = (arr, start=0, end=ar.length) => { let splitArray = (start, end) => { if (end - start <= 1) return; if (end - start === 2) { let temp = arr[start]; arr[start] = arr[start+1]; arr[start+1] = temp; } else{ reverseArrayInPlace(arr, start, end); } } let mergeArray = (start, mid, end) => { arr.splice(start, 0, ...arr.splice(mid, end - mid)); } let half = (start + end) >> 1; splitArray(start, half); splitArray(half, end); mergeArray(start, half, end); return arr; } let ar = [1, 5, 0, 4, 6]; console.log(reverseArrayInPlace(ar));Tampoco es necesario tratar el caso de la segunda base por separado. La operación funcionará bien si trata ese caso como un caso recursivo.
Aquí está su código alterado con esa idea:
let reverseArrayInPlace = (arr, start=0, end=ar.length) => { let splitArray = (start, end) => { if (end - start > 1) reverseArrayInPlace(arr, start, end); } let mergeArray = (start, mid, end) => { arr.splice(start, 0, ...arr.splice(mid, end - mid)); } let half = (start + end) >> 1; splitArray(start, half); splitArray(half, end); mergeArray(start, half, end); return arr; } let ar = [1, 5, 0, 4, 6]; console.log(reverseArrayInPlace(ar));