Dada una array arr[] , la tarea es imprimir la array obtenida al insertar elementos de arr[] uno por uno en una array inicialmente vacía, digamos arr1[] , e invertir la array arr1[] después de cada inserción.
Ejemplos:
Entrada: arr[] = {1, 2, 3, 4}
Salida: 4 2 1 3
Explicación:
Operaciones realizadas en el arreglo arr1[] de la siguiente manera:
Paso 1: Agregar 1 al arreglo e invertirlo. arr1[] = {1}
Paso 2: agregue 2 a la array e inviértalo. arr1[] = {2, 1}
Paso 3: agregue 3 en la array e inviértalo. arr1[] = {3, 1, 2}
Paso 3: agregue 4 en la array e inviértalo. arr1[] = {4, 2, 1, 3}Entrada: arr[] = {1, 2, 3}
Salida: 3 1 2
Explicación:
Operaciones realizadas en el arreglo arr1[] de la siguiente manera:
Paso 1: Agregar 1 al arreglo e invertirlo. arr1[] = {1}
Paso 2: agregue 2 a la array e inviértalo. arr1[] = {2, 1}
Paso 3: agregue 3 en la array e inviértalo. arr1[] = {3, 1, 2}
Enfoque ingenuo: el enfoque más simple para resolver el problema es iterar sobre la array arr[] e insertar cada elemento de arr[] uno por uno en la array arr1[] e invertir la array arr1[] después de cada inserción.
Complejidad de Tiempo: O(N 2 )
Espacio Auxiliar: O(1)
Enfoque eficiente: para optimizar el enfoque anterior, la idea es utilizar la cola de dos extremos (Deque) para agregar los elementos en ambos extremos. Siga los pasos a continuación para resolver el problema:
- Inicialice una cola de doble terminación para almacenar los elementos de la array convertida.
- Iterar sobre los elementos de la array arr[] y empujar los elementos al frente de Deque si el índice del elemento y la longitud del elemento tienen la misma paridad. De lo contrario, empújelo hacia la parte posterior del Deque .
- Finalmente, después de la iteración completa de la array arr[] , imprima el contenido de Deque como el arreglo de salida requerido.
A continuación se muestra la implementación del enfoque anterior:
C++
// C++ program of the above approach
#include <bits/stdc++.h>
using namespace std;
// Function to generate the array by
// inserting array elements one by one
// followed by reversing the array
void generateArray(int arr[], int n)
{
// Doubly ended Queue
deque<int> ans;
// Iterate over the array
for (int i = 0; i < n; i++) {
// Push array elements
// alternately to the front
// and back
if (i & 1)
ans.push_front(arr[i]);
else
ans.push_back(arr[i]);
}
// If size of list is odd
if (n & 1) {
// Reverse the list
reverse(ans.begin(),
ans.end());
}
// Print the elements
// of the array
for (auto x : ans) {
cout << x << " ";
}
cout << endl;
}
// Driver Code
int32_t main()
{
int n = 4;
int arr[n] = { 1, 2, 3, 4 };
generateArray(arr, n);
return 0;
}
Java
// Java program of the above approach
import java.io.*;
import java.util.*;
class GFG{
// Function to generate the array by
// inserting array elements one by one
// followed by reversing the array
static void generateArray(int arr[], int n)
{
// Doubly ended Queue
Deque<Integer> ans = new LinkedList<>();
// Iterate over the array
for(int i = 0; i < n; i++)
{
// Push array elements
// alternately to the front
// and back
if ((i & 1) != 0)
ans.addFirst(arr[i]);
else
ans.add(arr[i]);
}
// If size of list is odd
if ((n & 1) != 0)
{
// Reverse the list
Collections.reverse(Arrays.asList(ans));
}
// Print the elements
// of the array
for(int x : ans)
{
System.out.print(x + " ");
}
System.out.println();
}
// Driver Code
public static void main (String[] args)
{
int n = 4;
int arr[] = { 1, 2, 3, 4 };
generateArray(arr, n);
}
}
// This code is contributed by code_hunt
Python3
# Python3 program of the above approach from collections import deque # Function to generate the array by # inserting array elements one by one # followed by reversing the array def generateArray(arr, n): # Doubly ended Queue ans = deque() # Iterate over the array for i in range(n): # Push array elements # alternately to the front # and back if (i & 1 != 0): ans.appendleft(arr[i]) else: ans.append(arr[i]) # If size of list is odd if (n & 1 != 0): # Reverse the list ans.reverse() # Print the elements # of the array for x in ans: print(x, end = " ") print() # Driver Code n = 4 arr = [ 1, 2, 3, 4 ] generateArray(arr, n) # This code is contributed by code_hunt
C#
// C# program of
// the above approach
using System;
using System.Collections.Generic;
class GFG{
// Function to generate the array
// by inserting array elements
// one by one followed by
// reversing the array
static void generateArray(int []arr,
int n)
{
// Doubly ended Queue
List<int> ans = new List<int>();
// Iterate over the array
for(int i = 0; i < n; i++)
{
// Push array elements
// alternately to the front
// and back
if ((i & 1) != 0)
ans.Insert(0, arr[i]);
else
ans.Add(arr[i]);
}
// If size of list is odd
if ((n & 1) != 0)
{
// Reverse the list
ans.Reverse();
}
// Print the elements
// of the array
foreach(int x in ans)
{
Console.Write(x + " ");
}
Console.WriteLine();
}
// Driver Code
public static void Main(String[] args)
{
int n = 4;
int []arr = {1, 2, 3, 4};
generateArray(arr, n);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript program of the above approach
// Function to generate the array by
// inserting array elements one by one
// followed by reversing the array
function generateArray(arr, n)
{
// Doubly ended Queue
var ans = [];
// Iterate over the array
for (var i = 0; i < n; i++) {
// Push array elements
// alternately to the front
// and back
if (i & 1)
ans.splice(0,0,arr[i]);
else
ans.push(arr[i]);
}
// If size of list is odd
if (n & 1) {
// Reverse the list
ans.reverse();
}
// Print the elements
// of the array
ans.forEach(x => {
document.write( x + " ");
});
}
// Driver Code
var n = 4;
var arr = [1, 2, 3, 4];
generateArray(arr, n);
</script>
4 2 1 3
Complejidad temporal: O(N)
Espacio auxiliar: O(N)