Dada una matriz N que contiene al menos 5 elementos, quiero encontrar 2 números (P y Q) en los que 0 < P < Q < N - 1.
Supongamos que tenemos la siguiente matriz:
const N = [1, 9, 4, 5, 8]; De aquí la combinación que da el costo mínimo es P = 2 y Q = 3 .
Aquí está la solución que encontré y estoy buscando su ayuda si puedo mejorar su complejidad de tiempo:
function solution(N) { // since 0 < P < Q < N - 1 const sliced = N.slice(1, N.length - 1); const sorted = sliced.sort((a, b) => a - b); // the minimum should be from the start since we have sorted the array const P = 0; const Q = 1; return getCost(P, Q, sorted); } function getCost(P, Q, N) { return N[P] + N[Q]; } // output should be 9 console.log(solution([1, 9, 4, 5, 8]))En el mejor de los casos, es 0 (n log (n)) debido al tipo, pero me pregunto si podemos mejorarlo a O (n), por ejemplo.
Gracias por tu ayuda
¿Qué opinas de esta solución?
function solution([_, ...n]) { n.pop() n.sort((a, b) => a - b); return n[0] + n[1]; } // output should be 9 console.log(solution([1, 9, 4, 5, 8]))La lógica es la misma que usted describió, solo que usa algún otro enfoque que ofrece JS.
function twoSmallest(arr) { let [first, second] = [arr[1], arr[2]] for (let i = 3; i < arr.length - 1; i++) { const el = arr[i] if (el < first && el < second) { [first, second] = [Math.min(first, second), el] } else if (el < first) { [first, second] = [second, el] } else if (el < second) { second = el } } return first + second } Esta es una solución O(n) en el tiempo y O(1) en el espacio. También se asegura de que el elemento con el índice más pequeño se mantenga first en el caso de que necesite usar los índices y sea de interés por alguna razón.
El algoritmo es claro, en mi opinión, pero el código JS probablemente no sea la mejor implementación. No he escrito JS por algún tiempo.
Estoy bastante seguro de que esto es O(n):
const solution = (arr) => { // find smallest that's not at either end let idx = 1; let P = arr[1]; for(let i = 2; i < arr.length-1; i++) { if(arr[i] < P) { idx = i; P = arr[i]; } } // find second smallest that's not at either end let Q = Infinity; for(let i = 1; i < arr.length-1; i++) { if(i == idx) continue; if(arr[i] < Q) Q = arr[i]; } return P + Q; }