Programa Javascript para imprimir todos los tripletes en una array ordenada que forman AP

Dada una array ordenada de enteros positivos distintos, imprima todos los tripletes que forman
ejemplos AP (o progresión aritmética): 
 

Input : arr[] = { 2, 6, 9, 12, 17, 22, 31, 32, 35, 42 };
Output :
6 9 12
2 12 22
12 17 22
2 17 32
12 22 32
9 22 35
2 22 42
22 32 42

Input : arr[] = { 3, 5, 6, 7, 8, 10, 12};
Output :
3 5 7
5 6 7
6 7 8
6 8 10
8 10 12

Una solución simple es ejecutar tres bucles anidados para generar todos los tripletes y, para cada triplete, verificar si forma AP o no. La complejidad de tiempo de esta solución es O(n 3 )
Una mejor solución es usar hashing. Recorremos la array de izquierda a derecha. Consideramos cada elemento como medio y todos los elementos posteriores como elemento siguiente. Para buscar el elemento anterior, usamos una tabla hash.
 

Javascript

<script>
  
// JavaScript program to print all triplets in given
// array that form Arithmetic Progression
   
// Function to print all triplets in
// given sorted array that forms AP
function printAllAPTriplets( arr, n){
    const s = new Set()
    for (let i = 0; i < n - 1; i++)
    {
    for (let j = i + 1; j < n; j++)
    {
        // Use hash to find if there is
        // a previous element with difference
        // equal to arr[j] - arr[i]
        let diff = arr[j] - arr[i];
        if (s.has(arr[i] - diff))
            document.write(arr[i] - diff +" " + arr[i]
                 + " " + arr[j] + "<br>");
    }
    s.add(arr[i]);
    }
}
   
// Driver code
  
let arr = [ 2, 6, 9, 12, 17, 
                 22, 31, 32, 35, 42 ];
let n = arr.length;
printAllAPTriplets(arr, n);
  
</script>

Producción :  

6 9 12
2 12 22
12 17 22
2 17 32
12 22 32
9 22 35
2 22 42
22 32 42

Complejidad temporal: O(n 2
Espacio auxiliar: O(n)
Una solución eficiente se basa en el hecho de que la array está ordenada. Usamos el mismo concepto que se discutió en la pregunta del triplete GP . La idea es comenzar desde el segundo elemento y fijar cada elemento como un elemento medio y buscar los otros dos elementos en un triplete (uno más pequeño y otro más grande). 
A continuación se muestra la implementación de la idea anterior. 
 

Javascript

<script>
  
// JavaScript program to print all triplets in given
// array that form Arithmetic Progression
  
// Function to print all triplets in
// given sorted array that forms AP
function printAllAPTriplets(arr, n)
{
    for (let i = 1; i < n - 1; i++)
    {
  
        // Search other two elements of
        // AP with arr[i] as middle.
        for (let j = i - 1, k = i + 1; j >= 0 && k < n;)
        {
  
            // if a triplet is found
            if (arr[j] + arr[k] == 2 * arr[i])
            {
                document.write(arr[j] + " " + arr[i]
                    + " " + arr[k] + "<br>");
  
                // Since elements are distinct,
                // arr[k] and arr[j] cannot form
                // any more triplets with arr[i]
                k++;
                j--;
            }
  
            // If middle element is more move to
            // higher side, else move lower side.
            else if (arr[j] + arr[k] < 2 * arr[i])
                k++;        
            else
                j--;        
        }
    }
}
  
// Driver code
    let arr = [ 2, 6, 9, 12, 17,
                22, 31, 32, 35, 42 ];
    let n = arr.length;
    printAllAPTriplets(arr, n);
  
  
// This code is contributed by Surbhi Tyagi.
  
</script>

Producción :  

6 9 12
2 12 22
12 17 22
2 17 32
12 22 32
9 22 35
2 22 42
22 32 42

Complejidad de tiempo: O(n 2
Espacio auxiliar: O(1)
Consulte el artículo completo sobre Imprimir todos los tripletes en una array ordenada que forman AP para obtener más detalles.

Publicación traducida automáticamente

Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *