Dada una sorted array y un número x , encuentre un par en esa matriz cuya suma sea la más cercana a x". ¿Cómo podemos implementar esto con una complejidad de tiempo O(n) ?
Ejemplo:
fn([10,22,28,29,30,40], 54) // => [22, 30] fn([1,3,4,7,10], 15) // => [4, 10] fn([5], 7) // => [] fn([], 7) // => []Actualizar:
Fue mi último intento de resolver este problema, que no funciona y tiene una complejidad de tiempo O (n ^ 2).
function fn(arr, x) { let res = []; if (arr.length < 2) return res; for (let i = 0; i < arr.length - 1; i++) { for (let j = arr.length - 1; j > i; j--) { let t = Math.abs(arr[i] + arr[j] - x); if (arr[i] + arr[j] === x) return (res = [arr[i], arr[j]]); if (arr[i] + arr[j] > x) { if (t > Math.abs(arr[i] + arr[j] - x)) { t = Math.abs(arr[i] + arr[j] - x); res = [arr[i], arr[j]]; } } } } return res; } console.log(fn([10, 22, 28, 29, 30, 40], 54)); console.log(fn([1, 3, 4, 7, 10], 15));La idea basica es muy simple. Para seguir desde una posición muy segura, primero intentaremos con los números más lejanos.
1 2 3 4 5 ^ ^ lr Ahora tenemos diferentes casos. Seamos la diferencia entre la suma de dos num y el numero dado es d
Al principio permitiríamos cualquier d . Establézcalo en un número muy grande.
Entonces, si la suma de a[l]+a[r] < x , ¿entonces intenta aumentarla? Por lo tanto, sería lógico moverse hacia la derecha de la matriz ordenada (ascendente) l++
De lo contrario, si es a[l]+a[r] > x , r-- reduce la suma o muévete a la izquierda.
Si te preguntas por qué introduje d , tal vez pienses un poco. Pero sí, es solo para almacenar la diferencia. Entonces sería el valor absoluto de a[l]+a[r]-x .
Para ser más precisos, solo necesita ejecutarlo hasta que tenga l<r .
Lo resolví en código javascript:
function fn(arr, x) { let res = []; if (arr.length < 2) return res; let i = 0, j = arr.length - 1, t = Math.abs(arr[i] + arr[j] - x); while (i < j) { let s = arr[i] + arr[j]; if (s === t) { res = [arr[i], arr[j]]; break; } if (s < x) { i++; if (Math.abs(arr[i] + arr[j] - x) < t) { t = Math.abs(arr[i] + arr[j] - x); res = [arr[i], arr[j]]; } } if (s > x) { j--; if (Math.abs(arr[i] + arr[j] - x) < t) { t = Math.abs(arr[i] + arr[j] - x); res = [arr[i], arr[j]]; } } } return res; } console.log(fn([10, 22, 28, 29, 30, 40], 54)); console.log(fn([1, 3, 4, 7, 10], 15)); console.log(fn([5], 7)); console.log(fn([], 7));