Tengo algunos problemas para cambiar esta solución de O(n^2) a O(n). ¿Alguien puede ayudar amablemente? No puedo pensar en ninguna forma de hacer que la complejidad del tiempo sea O (n).
//MERGE SORTED ARRAY /*arr1 = [0,3,4,31] arr2 = [4,6,30]*/ const mergeSortedArrays = (arr1, arr2) => { let arr = []; let flag = true; // MERGING ARRAYS for (let i = 0; i < arr1.length; i++) { arr.push(arr1[i]);//PUSHING ARRAY1 in arr } for (let i = 0; i < arr2.length; i++) { arr.push(arr2[i]);//PUSING ARRAY2 in arr } //SORTING ARRAYS while (flag) { for (let i = 0; i < arr.length; i++) { if (arr[i] > arr[i + 1]) { let temp = arr[i + 1]; arr[i + 1] = arr[i]; arr[i] = temp; flag = true; } else { flag = false; } } } console.log(arr1); console.log(arr2); console.log(arr);//FINAL MERGED & SORTED ARRAY // return arr; } mergeSortedArrays([0, 3, 4, 31], [4, 6, 30]);Intenta visualizarlo. Es como si tuvieras dos pilas de cartas ordenadas que quisieras ordenar. Puede comparar las cartas en la parte superior de cada pila y poner el valor más pequeño en una tercera pila. Y repita hasta que todas las cartas estén en la tercera pila ordenada.
Puede mantener dos punteros, i y j , uno para cada matriz. Esto emulará una pila.
El algoritmo:
Repeat until the end of both arrays is reached: if arr1[i] <= arr2[j] push arr1[i] to the merged array and increment i else push arr2[j] to the merged array and increment jY algo de código javascript:
let merged = []; let i = 0; let j = 0; while(i < arr1.length || j < arr2.length){ if(j == arr2.length || (i < arr1.length && arr1[i] <= arr2[j])){ merged.push(arr1[i]); i++; } else{ merged.push(arr2[j]); j++; } }Puede usar el método de dos punteros (esta solución se basa en la suposición de que las dos listas siempre estarán ordenadas):
let p1 = 0, p2 = 0; let arr = []; while (p1 < arr1.length && p2 < arr2.length) { if (arr1[p1] < arr2[p2]) arr.push(arr1[p1++]); else arr.push(arr2[p2++]); } while (p1 < arr1.length) arr.push(arr1[p1++]); while (p2 < arr2.length) arr.push(arr2[p2++]);Este código se ejecutará en la complejidad de tiempo de O(N).
Respuesta actualizada basada en comentarios del uso de Array#sort() para:
const mergeSortedArrays = (arr1, arr2) => { const array = { arr1, arr2 } const index = { a1: 0, a2: 0 } const length = { a1: array.arr1.length, a2: array.arr2.length } const merged = [] let current = 0 while (current < length.a1 + length.a2) { const [a, i] = !(index.a1 >= length.a1) && (index.a2 >= length.a2 || array.arr1[index.a1] < array.arr2[index.a2]) ? ['arr1', 'a1'] : ['arr2', 'a2'] merged[current] = array[a][index[i]] index[i]++ current++ } return merged } const result = mergeSortedArrays([0, 3, 4, 31], [4, 6, 30]) console.log(result)