array circular – Part 1

Una array se llama circular si consideramos el primer elemento como el siguiente del último elemento. Las arrays circulares se utilizan para implementar la cola (consulte this y this ).
Un problema de ejemplo: 
supongamos que n personas están sentadas en una mesa circular con los nombres A, B, C, D, … Dado un nombre, necesitamos imprimir todas las n personas (en orden) comenzando por el nombre dado. 
                                      

 Por ejemplo, considere 6 personas ABCDEF y el nombre dado como ‘D’. Las personas sentadas en forma circular a partir de D son DEFAB C.
Una solución simple es crear una array auxiliar de tamaño 2*n y almacenarla en otra array. Por ejemplo, para 6 personas, creamos debajo de la array auxiliar. 
ABCDEFABCDEF 
Ahora, para cualquier índice dado, simplemente imprimimos n elementos a partir de él. Por ejemplo, imprimimos los siguientes 6. 
ABC DEFABC DEF 

A continuación se muestra la implementación del enfoque anterior. 

// CPP program to demonstrate use of circular
// array using extra memory space
#include <bits/stdc++.h>
using namespace std;
void print(char a[], int n, int ind)
{
    // Create an auxiliary array of twice size.
    char b[(2 * n)];
 
    // Copy a[] to b[] two times
    for (int i = 0; i < n; i++)
        b[i] = b[n + i] = a[i];
 
    // print from ind-th index to (n+i)th index.
    for (int i = ind; i < n + ind; i++)
        cout << b[i] << " ";
}
 
// Driver code
int main()
{
    char a[] = { 'A', 'B', 'C', 'D', 'E', 'F' };
    int n = sizeof(a) / sizeof(a[0]);
    print(a, n, 3);
    return 0;
}

// Java program to demonstrate use of circular
// array using extra memory space
import java.util.*;
import java.lang.*;
 
public class GfG{
     
    public static void print(char a[], int n,
                                  int ind){
     
        // Create an auxiliary array
        // of twice size.
        char[] b = new char[(2 * n)];
 
        // Copy a[] to b[] two times
        for (int i = 0; i < n; i++)
            b[i] = b[n + i] = a[i];
 
        // print from ind-th index to
        // (n+i)th index.
        for (int i = ind; i < n + ind; i++)
            System.out.print(b[i]+" ");
    }
     
    // Driver code
    public static void main(String argc[]){
        char[] a = new char[]{ 'A', 'B', 'C',
                             'D', 'E', 'F' };
        int n = 6;
        print(a, n, 3);
    }
}
 
/* This code is contributed by Sagar Shukla */

# Python3 program to demonstrate use of
# circular array using extra memory space
 
def prints(a, n, ind):
     
    # Create an auxiliary array of twice size.
    b = [None]*2*n
    i = 0
     
    # Copy a[] to b[] two times
    while i < n:
        b[i] = b[n + i] = a[i]
        i = i + 1
     
    i = ind
 
    # print from ind-th index to (n+i)th index.
    while i < n + ind :
        print(b[i], end = " ");
        i = i + 1
 
# Driver Code
a = ['A', 'B', 'C', 'D', 'E', 'F']
n = len(a);
prints(a, n, 3);
 
#This code is contributed by rishabh_jain

// C# program to demonstrate use of circular
// array using extra memory space
using System;
 
public class GfG {
 
    public static void print(char[] a, int n,
                                     int ind)
    {
        // Create an auxiliary array
        // of twice size.
        char[] b = new char[(2 * n)];
 
        // Copy a[] to b[] two times
        for (int i = 0; i < n; i++)
            b[i] = b[n + i] = a[i];
 
        // print from ind-th index to
        // (n+i)th index.
        for (int i = ind; i < n + ind; i++)
            Console.Write(b[i] + " ");
    }
 
    // Driver code
    public static void Main()
    {
        char[] a = new char[] { 'A', 'B', 'C',
                                'D', 'E', 'F' };
        int n = 6;
        print(a, n, 3);
    }
}
 
/* This code is contributed by vt_m*/

<script>
// javascript program to demonstrate use of circular
// array using extra memory space
 
 
    function print( a , n , ind) {
 
        // Create an auxiliary array
        // of twice size.
        var b = Array(2 * n);
 
        // Copy a to b two times
        for (i = 0; i < n; i++)
            b[i] = b[n + i] = a[i];
 
        // print from ind-th index to
        // (n+i)th index.
        for (i = ind; i < n + ind; i++)
            document.write(b[i] + " ");
    }
 
    // Driver code
     
        var a = [ 'A', 'B', 'C', 'D', 'E', 'F' ];
        var n = 6;
        print(a, n, 3);
 
// This code is contributed by todaysgaurav
</script>

Producción:  

D E F A B C 

Este enfoque toma tiempo O(n) pero toma espacio adicional de orden O(n)

Una solución eficiente es tratar con arreglos circulares usando el mismo arreglo. Si se ejecuta una observación cuidadosa a través de la array, luego del índice n-ésimo, el siguiente índice siempre comienza desde 0, por lo que al usar el operador mod , podemos acceder fácilmente a los elementos de la lista circular, si usamos (i)%n y ejecute el bucle desde el i-ésimo índice hasta el n+i-ésimo índice. y aplicar mod podemos hacer el recorrido en una array circular dentro de la array dada sin usar ningún espacio adicional. 

// CPP program to demonstrate the use of circular
// array without using extra memory space
#include <bits/stdc++.h>
using namespace std;
 
// function to print circular list starting
// from given index ind.
void print(char a[], int n, int ind)
{
    // print from ind-th index to (n+i)th index.
    for (int i = ind; i < n + ind; i++)
        cout << a[(i % n)] << " ";
}
 
// Driver code
int main()
{
    char a[] = { 'A', 'B', 'C', 'D', 'E', 'F' };
    int n = sizeof(a) / sizeof(a[0]);
    print(a, n, 3);
    return 0;
}

// Java program to demonstrate use of circular
// array using extra memory space
import java.util.*;
import java.lang.*;
 
public class GfG{
     
    // function to print circular list
    // starting from given index ind.
    public static void print(char a[], int n,
                                   int ind){
         
        // print from ind-th index to
        // (n+i)th index.
        for (int i = ind; i < n + ind; i++)
            System.out.print(a[(i % n)] + " ");
    }
     
    // driver code
    public static void main(String argc[]){
        char[] a = new char[]{ 'A', 'B', 'C',
                             'D', 'E', 'F' };
        int n = 6;
        print(a, n, 3);
    }
}
 
/* This code is contributed by Sagar Shukla */

# Python3 program to demonstrate the use of
# circular array without using extra memory space
 
# function to print circular list starting
# from given index ind.
def prints(a, n, ind):
    i = ind
     
    # print from ind-th index to (n+i)th index.
    while i < n + ind :
        print(a[(i % n)], end = " ")
        i = i + 1
 
# Driver Code
a = ['A', 'B', 'C', 'D', 'E', 'F']
n = len(a);
prints(a, n, 3);
 
# This code is contributed by rishabh_jain

// C# program to demonstrate use of circular
// array without using extra memory space
using System;
 
public class GfG {
 
    // function to print circular list
    // starting from given index ind.
    public static void print(char[] a, int n,
                                     int ind)
    {
        // print from ind-th index to
        // (n+i)th index.
        for (int i = ind; i < n + ind; i++)
            Console.Write(a[(i % n)] + " ");
    }
 
    // driver code
    public static void Main()
    {
        char[] a = new char[] { 'A', 'B', 'C',
                                'D', 'E', 'F' };
        int n = 6;
        print(a, n, 3);
    }
}
 
/* This code is contributed by vt_m */

<?php
// PHP program to demonstrate use
// of circular array without using
// extra memory space
 
// function to print circular list
// starting from given index ind.
function print($a, $n, $ind)
{
    // print from ind-th index
    // to (n+i)th index.
    for ($i = $ind; $i < $n + $ind; $i++)
        echo $a[($i % $n)] . " ";
}
 
// Driver Code
$a = array( 'A', 'B', 'C',
            'D', 'E', 'F' );
$n = count($a);
print($a, $n, 3);
 
// This code is contributed by Sam007
?>

<script>
// javascript program to demonstrate use of circular
// array using extra memory space
 
    // function to print circular list
    // starting from given index ind.
    function print(a, n, ind)
    {
 
        // print from ind-th index to
        // (n+i)th index.
        for (var i = ind; i < n + ind; i++)
            document.write(a[parseInt(i % n)] + " ");
    }
 
    // Driver code
        var a =[ 'A', 'B', 'C', 'D', 'E', 'F' ];
        var n = 6;
        print(a, n, 3);
 
// This code is contributed by Rajput-Ji
</script>

Producción :  

D E F A B C 

Este enfoque requiere O(n) tiempo y O(1) espacio adicional.
Más problemas basados ​​en array circular: 

• Suma de subarreglo circular máxima
• Maximizar la suma de diferencias consecutivas en una array circular
• Implementación de Deque usando array circular
• Cola circular | Conjunto 1 (Introducción e implementación de arrays)
• Cola circular | Conjunto 2 (Implementación de lista enlazada circular)
• Encuentre la subsecuencia creciente más larga de manera circular
• Diferencia absoluta mínima de elementos adyacentes en una array circular

Artículos recientes sobre array circular.