Dada una array, invierta cada sub-array que satisfaga las restricciones dadas.
Hemos discutido una solución donde invertimos cada subarreglo formado por k elementos consecutivos en el Conjunto 1 . En este conjunto, discutiremos varias variaciones interesantes de este problema.
Variación 1 (Grupos alternativos inversos): Invierte cada subarreglo alternativo formado por k elementos consecutivos.
Ejemplos:
Input: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9] k = 3 Output: [3, 2, 1, 4, 5, 6, 9, 8, 7] Input: arr = [1, 2, 3, 4, 5, 6, 7, 8] k = 2 Output: [2, 1, 3, 4, 6, 5, 7, 8]
A continuación se muestra la implementación:
C++
// C++ program to reverse every alternate sub-array
// formed by consecutive k elements
#include <iostream>
using namespace std;
// Function to reverse every alternate sub-array
// formed by consecutive k elements
void reverse(int arr[], int n, int k)
{
// increment i in multiples of 2*k
for (int i = 0; i < n; i += 2*k)
{
int left = i;
// to handle case when 2*k is not multiple of n
int right = min(i + k - 1, n - 1);
// reverse the sub-array [left, right]
while (left < right)
swap(arr[left++], arr[right--]);
}
}
// Driver code
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
int k = 3;
int n = sizeof(arr) / sizeof(arr[0]);
reverse(arr, n, k);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Java
// Java program to reverse
// every alternate sub-array
// formed by consecutive k elements
class GFG
{
// Function to reverse every
// alternate sub-array formed
// by consecutive k elements
static void reverse(int arr[], int n, int k)
{
// increment i in multiples of 2*k
for (int i = 0; i < n; i += 2 * k)
{
int left = i;
// to handle case when 2*k is not multiple of n
int right = Math.min(i + k - 1, n - 1);
// reverse the sub-array [left, right]
while (left < right) {
swap(arr, left++, right--);
}
}
}
static int[] swap(int[] array, int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
return array;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11, 12, 13, 14};
int k = 3;
int n = arr.length;
reverse(arr, n, k);
for (int i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
}
}
// This code has been contributed by 29AjayKumar
Python3
# Python3 program to reverse every alternate sub-array # formed by consecutive k elements # Function to reverse every alternate sub-array # formed by consecutive k elements def reverse(arr, n, k): # increment i in multiples of 2*k for i in range(0,n,2*k): left = i # to handle case when 2*k is not multiple of n right = min(i + k - 1, n - 1) # reverse the sub-array [left, right] while (left < right): temp = arr[left] arr[left] = arr[right] arr[right] = temp left += 1 right -= 1 # Driver code if __name__ == '__main__': arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14] k = 3 n = len(arr) reverse(arr, n, k) for i in range(0,n,1): print(arr[i],end =" ") # This code is contributed by # Surendra_Gangwar
C#
// C# program to reverse every alternate
// sub-array formed by consecutive k elements
using System;
class GFG
{
// Function to reverse every
// alternate sub-array formed
// by consecutive k elements
static void reverse(int []arr,
int n, int k)
{
// increment i in multiples of 2*k
for (int i = 0; i < n; i += 2 * k)
{
int left = i;
// to handle case when 2*k is
// not multiple of n
int right = Math.Min(i + k - 1, n - 1);
// reverse the sub-array [left, right]
while (left < right)
{
swap(arr, left++, right--);
}
}
}
static int[] swap(int[] array, int i, int j)
{
int temp = array[i];
array[i] = array[j];
array[j] = temp;
return array;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11, 12, 13, 14};
int k = 3;
int n = arr.Length;
reverse(arr, n, k);
for (int i = 0; i < n; i++)
{
Console.Write(arr[i] + " ");
}
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// Javascript program to reverse
// every alternate sub-array
// formed by consecutive k elements
// Function to reverse every
// alternate sub-array formed
// by consecutive k elements
function reverse(arr, n, k)
{
// Increment i in multiples of 2*k
for(let i = 0; i < n; i += 2 * k)
{
let left = i;
// To handle case when 2*k is
// not multiple of n
let right = Math.min(i + k - 1,
n - 1);
// reverse the sub-array [left, right]
while (left < right)
{
swap(arr, left++, right--);
}
}
}
function swap(array, i, j)
{
let temp = array[i];
array[i] = array[j];
array[j] = temp;
return array;
}
// Driver code
let arr = [ 1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11, 12, 13, 14 ];
let k = 3;
let n = arr.length;
reverse(arr, n, k);
for(let i = 0; i < n; i++)
{
document.write(arr[i] + " ");
}
// This code is contributed by rag2127
</script>
Producción
3 2 1 4 5 6 9 8 7 10 11 12 14 13
Variación 2 (Reversa a distancia dada): Invierte cada subarreglo formado por k elementos consecutivos separados por una distancia dada.
Ejemplos:
Input: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] k = 3 m = 2 Output: [3, 2, 1, 4, 5, 8, 7, 6, 9, 10] Input: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] k = 3 m = 1 Output: [3, 2, 1, 4, 7, 6, 5, 8, 10, 9] Input: arr = [1, 2, 3, 4, 5, 6, 7, 8] k = 2 m = 0 Output: [2, 1, 4, 3, 6, 5, 8, 7]
A continuación se muestra su implementación:
C++
// C++ program to reverse every sub-array formed by
// consecutive k elements at given distance apart
#include <iostream>
using namespace std;
// Function to reverse every sub-array formed by
// consecutive k elements at m distance apart
void reverse(int arr[], int n, int k, int m)
{
// increment i in multiples of k + m
for (int i = 0; i < n; i += k + m)
{
int left = i;
// to handle case when k + m is not multiple of n
int right = min(i + k - 1, n - 1);
// reverse the sub-array [left, right]
while (left < right)
swap(arr[left++], arr[right--]);
}
}
// Driver code
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14};
int k = 3;
int m = 2;
int n = sizeof(arr) / sizeof(arr[0]);
reverse(arr, n, k, m);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Java
// java program to reverse every sub-array formed by
// consecutive k elements at given distance apart
class GFG
{
// Function to reverse every sub-array formed by
// consecutive k elements at m distance apart
static void reverse(int[] arr, int n, int k, int m)
{
// increment i in multiples of k + m
for (int i = 0; i < n; i += k + m)
{
int left = i;
// to handle case when k + m is not multiple of n
int right = Math.min(i + k - 1, n - 1);
// reverse the sub-array [left, right]
while (left < right)
swap(arr,left++, right--);
}
}
static int[] swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11, 12, 13, 14};
int k = 3;
int m = 2;
int n = arr.length;
reverse(arr, n, k, m );
for (int i = 0; i < n; i++)
{
System.out.print(arr[i] + " ");
}
}
}
// This code has been contributed by Rajput-Ji
Python3
# Python3 program to reverse every # sub-array formed by consecutive # k elements at given distance apart # Function to reverse every # sub-array formed by consecutive # k elements at m distance apart def reverse(arr, n, k, m): # increment i in multiples of k + m for i in range(0, n, k + m): left = i; # to handle case when k + m # is not multiple of n right = min(i + k - 1, n - 1); # reverse the sub-array [left, right] while (left < right): arr = swap(arr,left, right); left += 1; right -= 1; return arr; def swap(arr, i, j): temp = arr[i]; arr[i] = arr[j]; arr[j] = temp; return arr; # Driver code arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14]; k = 3; m = 2; n = len(arr); arr = reverse(arr, n, k, m ); for i in range(0, n): print(arr[i], end = " "); # This code is contributed by Rajput-Ji
C#
// C# program to reverse every sub-array
// formed by consecutive k elements at
// given distance apart
using System;
class GFG
{
// Function to reverse every sub-array
// formed by consecutive k elements
// at m distance apart
static void reverse(int[] arr, int n,
int k, int m)
{
// increment i in multiples of k + m
for (int i = 0; i < n; i += k + m)
{
int left = i;
// to handle case when k + m is
// not multiple of n
int right = Math.Min(i + k - 1, n - 1);
// reverse the sub-array [left, right]
while (left < right)
swap(arr, left++, right--);
}
}
static int[] swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11, 12, 13, 14};
int k = 3;
int m = 2;
int n = arr.Length;
reverse(arr, n, k, m );
for (int i = 0; i < n; i++)
{
Console.Write(arr[i] + " ");
}
}
}
// This code is contributed by PrinciRaj1992
Javascript
<script>
// javascript program to reverse every sub-array formed by
// consecutive k elements at given distance apart
// Function to reverse every sub-array formed by
// consecutive k elements at m distance apart
function reverse(arr,n,k,m)
{
// increment i in multiples of k + m
for (let i = 0; i < n; i += k + m)
{
let left = i;
// to handle case when k + m is not multiple of n
let right = Math.min(i + k - 1, n - 1);
// reverse the sub-array [left, right]
while (left < right)
swap(arr,left++, right--);
}
}
function swap(arr,i,j)
{
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// Driver code
let arr=[1, 2, 3, 4, 5, 6, 7, 8,
9, 10, 11, 12, 13, 14];
let k = 3;
let m = 2;
let n = arr.length;
reverse(arr, n, k, m );
for (let i = 0; i < n; i++)
{
document.write(arr[i] + " ");
}
// This code is contributed by ab2127
</script>
Producción
3 2 1 4 5 8 7 6 9 10 13 12 11 14
Variación 3 (Revertir duplicando el tamaño del grupo):
Invierta cada subarreglo formado por k elementos consecutivos donde k se duplica con cada subarreglo.
Ejemplos:
Input: arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] k = 1 Output: [1], [3, 2], [7, 6, 5, 4], [15, 14, 13, 12, 11, 10, 9, 8]
A continuación se muestra su implementación:
C++
// C++ program to reverse every sub-array formed by
// consecutive k elements where k doubles itself with
// every sub-array.
#include <iostream>
using namespace std;
// Function to reverse every sub-array formed by
// consecutive k elements where k doubles itself
// with every sub-array.
void reverse(int arr[], int n, int k)
{
// increment i in multiples of k where value
// of k is doubled with each iteration
for (int i = 0; i < n; i += k/2)
{
int left = i;
// to handle case when number of elements in
// last group is less than k
int right = min(i + k - 1, n - 1);
// reverse the sub-array [left, right]
while (left < right)
swap(arr[left++], arr[right--]);
// double value of k with each iteration
k = k*2;
}
}
// Driver code
int main()
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
int k = 1;
int n = sizeof(arr) / sizeof(arr[0]);
reverse(arr, n, k);
for (int i = 0; i < n; i++)
cout << arr[i] << " ";
return 0;
}
Java
// Java program to reverse every sub-array
// formed by consecutive k elements where
// k doubles itself with every sub-array.
import java.util.*;
class GFG
{
// Function to reverse every sub-array formed by
// consecutive k elements where k doubles itself
// with every sub-array.
static void reverse(int arr[], int n, int k)
{
// increment i in multiples of k where value
// of k is doubled with each iteration
for (int i = 0; i < n; i += k / 2)
{
int left = i;
// to handle case when number of elements in
// last group is less than k
int right = Math.min(i + k - 1, n - 1);
// reverse the sub-array [left, right]
while (left < right)
swap(arr, left++, right--);
// double value of k with each iteration
k = k * 2;
}
}
static int[] swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// Driver code
public static void main(String[] args)
{
int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, 12, 13, 14, 15, 16};
int k = 1;
int n = arr.length;
reverse(arr, n, k);
for (int i = 0; i < n; i++)
System.out.print(arr[i] + " ");
}
}
// This code is contributed by 29AjayKumar
Python3
# Python3 program to reverse every # sub-array formed by consecutive # k elements where k doubles itself # with every sub-array # Function to reverse every sub-array # formed by consecutive k elements # where k doubles itself with every # sub-array def reverse(arr, n, k): i = 0 # Increment i in multiples of k where # value of k is doubled with each # iteration while (i < n): left = i # To handle case when number of elements # in last group is less than k right = min(i + k - 1, n - 1) # Reverse the sub-array [left, right] while (left < right): arr[left], arr[right] = arr[right], arr[left] left += 1 right -= 1 # Double value of k with each iteration k = k * 2 i += int(k / 2) # Driver code arr = [ 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16] k = 1 n = len(arr) reverse(arr, n, k) print(*arr, sep = ' ') # This code is contributed by avanitrachhadiya2155
C#
// C# program to reverse every sub-array
// formed by consecutive k elements where
// k doubles itself with every sub-array.
using System;
class GFG
{
// Function to reverse every sub-array formed by
// consecutive k elements where k doubles itself
// with every sub-array.
static void reverse(int []arr, int n, int k)
{
// increment i in multiples of k where value
// of k is doubled with each iteration
for (int i = 0; i < n; i += k / 2)
{
int left = i;
// to handle case when number of elements in
// last group is less than k
int right = Math.Min(i + k - 1, n - 1);
// reverse the sub-array [left, right]
while (left < right)
swap(arr, left++, right--);
// double value of k with each iteration
k = k * 2;
}
}
static int[] swap(int[] arr, int i, int j)
{
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// Driver code
public static void Main(String[] args)
{
int []arr = {1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, 12, 13, 14, 15, 16};
int k = 1;
int n = arr.Length;
reverse(arr, n, k);
for (int i = 0; i < n; i++)
Console.Write(arr[i] + " ");
}
}
// This code is contributed by Rajput-Ji
Javascript
<script>
// Javascript program to reverse every sub-array
// formed by consecutive k elements where
// k doubles itself with every sub-array.
// Function to reverse every sub-array formed by
// consecutive k elements where k doubles itself
// with every sub-array.
function reverse(arr,n,k)
{
// increment i in multiples of k where value
// of k is doubled with each iteration
for (let i = 0; i < n; i += k / 2)
{
let left = i;
// to handle case when number of elements in
// last group is less than k
let right = Math.min(i + k - 1, n - 1);
// reverse the sub-array [left, right]
while (left < right)
swap(arr, left++, right--);
// double value of k with each iteration
k = k * 2;
}
}
function swap(arr,i,j)
{
let temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
return arr;
}
// Driver code
let arr=[1, 2, 3, 4, 5, 6, 7, 8, 9,
10, 11, 12, 13, 14, 15, 16];
let k = 1;
let n = arr.length;
reverse(arr, n, k);
document.write(arr.join(" "));
// This code is contributed by unknown2108
</script>
Producción
1 3 2 7 6 5 4 15 14 13 12 11 10 9 8 16
La complejidad temporal de todas las soluciones discutidas anteriormente es O(n).
El espacio auxiliar utilizado por el programa es O(1).
Este artículo es una contribución de Aditya Goel . Si te gusta GeeksforGeeks y te gustaría contribuir, también puedes escribir un artículo usando write.geeksforgeeks.org o enviar tu artículo por correo a review-team@geeksforgeeks.org. Vea su artículo que aparece en la página principal de GeeksforGeeks y ayude a otros Geeks.
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