• Jobs
  • About Us
  • professionals
    • Home
    • Jobs
    • Courses and challenges
  • business
    • Home
    • Post vacancy
    • Our process
    • Pricing
    • Assessments
    • Payroll
    • Blog
    • Sales
    • Salary Calculator

0

211
Views
¿Cómo encontrar un par de números en la matriz cuya suma es más cercana a x con una complejidad de tiempo O (n)?

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));

about 3 years ago · Juan Pablo Isaza
2 answers
Answer question

0

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 .

about 3 years ago · Juan Pablo Isaza Report

0

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));

about 3 years ago · Juan Pablo Isaza Report
Answer question
Find remote jobs

Discover the new way to find a job!

Top jobs
Top job categories
Business
Post vacancy Pricing Our process Sales
Legal
Terms and conditions Privacy policy
© 2025 PeakU Inc. All Rights Reserved.

Andres GPT

Recommend me some offers
I have an error