Dada una string, mueva todos los elementos colocados pares al final de la string. Mientras mueve elementos, mantenga el mismo orden relativo de todos los elementos en posiciones pares e impares. Por ejemplo, si la string dada es «a1b2c3d4e5f6g7h8i9j1k2l3m4», conviértala en «abcdefghijklm1234567891234» en el lugar y en complejidad de tiempo O(n).
A continuación se muestran los pasos:
- Recorte la substring de prefijo más grande del tamaño de la forma 3^k + 1. En este paso, encontramos el entero no negativo más grande k tal que 3^k+1 es menor o igual que n (longitud de la cuerda)
- Aplique el algoritmo de iteración del líder del ciclo (se ha discutido a continuación), comenzando con el índice 1, 3, 9…… a esta substring. El algoritmo de iteración del líder del ciclo mueve todos los elementos de esta substring a sus posiciones correctas, es decir, todos los alfabetos se desplazan a la mitad izquierda de la substring y todos los dígitos se desplazan a la mitad derecha de esta substring.
- Procese la substring restante de forma recursiva utilizando los pasos n.° 1 y n.° 2.
- Ahora, solo necesitamos unir las substrings procesadas. Comience desde cualquier extremo (por ejemplo, desde la izquierda), elija dos substrings y aplique los pasos a continuación:
…. 4.1 Invierta la segunda mitad de la primera substring.
…. 4.2 Invierta la primera mitad de la segunda substring.
…. 4.3 Invierta la segunda mitad de la primera substring y la primera mitad de la segunda substring juntas.- Repita el paso 4 hasta que se unan todas las substrings. Es similar a la fusión de k-way donde la primera substring se une con la segunda. La resultante se fusiona con la tercera y así sucesivamente.
Entendámoslo con un ejemplo:
Tenga en cuenta que hemos utilizado valores como 10, 11 12 en el siguiente ejemplo. Considere estos valores solo como caracteres individuales. Estos valores se utilizan para mejorar la legibilidad.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 a 1 b 2 c 3 d 4 e 5 f 6 g 7 h 8 i 9 j 10 k 11 l 12 m 13
Después de dividirse en el tamaño de la forma 3^k + 1, se forman dos substrings de tamaño 10 cada una. La tercera substring está formada por el tamaño 4 y la cuarta substring está formada por el tamaño 2.
0 1 2 3 4 5 6 7 8 9 a 1 b 2 c 3 d 4 e 5 10 11 12 13 14 15 16 17 18 19 f 6 g 7 h 8 i 9 j 10 20 21 22 23 k 11 l 12 24 25 m 13
Después de aplicar el algoritmo de iteración del líder del ciclo a la primera substring:
0 1 2 3 4 5 6 7 8 9 a b c d e 1 2 3 4 5 10 11 12 13 14 15 16 17 18 19 f 6 g 7 h 8 i 9 j 10 20 21 22 23 k 11 l 12 24 25 m 13
Después de aplicar el algoritmo de iteración del líder del ciclo a la segunda substring:
0 1 2 3 4 5 6 7 8 9 a b c d e 1 2 3 4 5 10 11 12 13 14 15 16 17 18 19 f g h i j 6 7 8 9 10 20 21 22 23 k 11 l 12 24 25 m 13
Después de aplicar el algoritmo de iteración del líder del ciclo a la tercera substring:
0 1 2 3 4 5 6 7 8 9 a b c d e 1 2 3 4 5 10 11 12 13 14 15 16 17 18 19 f g h i j 6 7 8 9 10 20 21 22 23 k l 11 12 24 25 m 13
Después de aplicar el algoritmo de iteración del líder del ciclo a la cuarta substring:
0 1 2 3 4 5 6 7 8 9 a b c d e 1 2 3 4 5 10 11 12 13 14 15 16 17 18 19 f g h i j 6 7 8 9 10 20 21 22 23 k l 11 12 24 25 m 13
Unión de la primera substring y la segunda substring:
1. La segunda mitad de la primera substring y la primera mitad de la segunda substring se invierten.
0 1 2 3 4 5 6 7 8 9 a b c d e 5 4 3 2 1 <--------- First Sub-string 10 11 12 13 14 15 16 17 18 19 j i h g f 6 7 8 9 10 <--------- Second Sub-string 20 21 22 23 k l 11 12 24 25 m 13
2. La segunda mitad de la primera substring y la primera mitad de la segunda substring se invierten juntas (están fusionadas, es decir, ahora solo hay tres substrings).
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 a b c d e f g h i j 1 2 3 4 5 6 7 8 9 10 20 21 22 23 k l 11 12 24 25 m 13
Unión de la primera substring y la segunda substring:
1. La segunda mitad de la primera substring y la primera mitad de la segunda substring se invierten.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 a b c d e f g h i j 10 9 8 7 6 5 4 3 2 1 <--------- First Sub-string 20 21 22 23 l k 11 12 <--------- Second Sub-string 24 25 m 13
2. La segunda mitad de la primera substring y la primera mitad de la segunda substring se invierten juntas (están fusionadas, es decir, ahora solo hay dos substrings).
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 a b c d e f g h i j k l 1 2 3 4 5 6 7 8 9 10 11 12 24 25 m 13
Unión de la primera substring y la segunda substring:
1. La segunda mitad de la primera substring y la primera mitad de la segunda substring se invierten.
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 a b c d e f g h i j k l 12 11 10 9 8 7 6 5 4 3 2 1 <----- First Sub-string 24 25 m 13 <----- Second Sub-string
2. La segunda mitad de la primera substring y la primera mitad de la segunda substring se invierten juntas (están fusionadas, es decir, ahora solo hay una substring).
0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 a b c d e f g h i j k l m 1 2 3 4 5 6 7 8 9 10 11 12 13
Dado que todas las substrings se han unido, hemos terminado.
¿Cómo funciona el algoritmo de iteración del líder del ciclo?
Entendámoslo con un ejemplo:
Input: 0 1 2 3 4 5 6 7 8 9 a 1 b 2 c 3 d 4 e 5 Output: 0 1 2 3 4 5 6 7 8 9 a b c d e 1 2 3 4 5 Old index New index 0 0 1 5 2 1 3 6 4 2 5 7 6 3 7 8 8 4 9 9
Sea len la longitud de la cuerda. Si observamos cuidadosamente, encontramos que el nuevo índice viene dado por la siguiente fórmula:
if( oldIndex is odd )
newIndex = len / 2 + oldIndex / 2;
else
newIndex = oldIndex / 2;
Entonces, el problema se reduce a cambiar los elementos a nuevos índices basados en la fórmula anterior.
El algoritmo de iteración del líder del ciclo se aplicará a partir de los índices de la forma 3^k, comenzando con k = 0.
A continuación se muestran los pasos:
- Encuentre una nueva posición para el elemento en la posición i. Antes de colocar este elemento en la nueva posición, mantenga la copia de seguridad del elemento en la nueva posición. Ahora, coloque el elemento en la nueva posición.
- Repita el paso 1 para la nueva posición hasta que se complete un ciclo, es decir, hasta que el procedimiento vuelva a la posición inicial.
- Aplique el algoritmo de iteración del líder del ciclo al siguiente índice de la forma 3^k. Repita este paso hasta que 3^k < len.
Consider input array of size 28: The first cycle leader iteration, starting with index 1: 1->14->7->17->22->11->19->23->25->26->13->20->10->5->16->8->4->2->1 The second cycle leader iteration, starting with index 3: 3->15->21->24->12->6->3 The third cycle leader iteration, starting with index 9: 9->18->9
Basado en el algoritmo anterior, a continuación se muestra el código:
C++
// C++ implementation of above approach
#include <bits/stdc++.h>
using namespace std;
// A utility function to swap characters
void swap ( char* a, char* b )
{
char t = *a;
*a = *b;
*b = t;
}
// A utility function to reverse string str[low..high]
void reverse ( char* str, int low, int high )
{
while ( low < high )
{
swap( &str[low], &str[high] );
++low;
--high;
}
}
// Cycle leader algorithm to move all even
// positioned elements at the end.
void cycleLeader ( char* str, int shift, int len )
{
int j;
char item;
for (int i = 1; i < len; i *= 3 )
{
j = i;
item = str[j + shift];
do
{
// odd index
if ( j & 1 )
j = len / 2 + j / 2;
// even index
else
j /= 2;
// keep the back-up of element at new position
swap (&str[j + shift], &item);
}
while ( j != i );
}
}
// The main function to transform a string. This function
// mainly uses cycleLeader() to transform
void moveNumberToSecondHalf( char* str )
{
int k, lenFirst;
int lenRemaining = strlen( str );
int shift = 0;
while ( lenRemaining )
{
k = 0;
// Step 1: Find the largest prefix
// subarray of the form 3^k + 1
while ( pow( 3, k ) + 1 <= lenRemaining )
k++;
lenFirst = pow( 3, k - 1 ) + 1;
lenRemaining -= lenFirst;
// Step 2: Apply cycle leader algorithm
// for the largest subarrau
cycleLeader ( str, shift, lenFirst );
// Step 4.1: Reverse the second half of first subarray
reverse ( str, shift / 2, shift - 1 );
// Step 4.2: Reverse the first half of second sub-string.
reverse ( str, shift, shift + lenFirst / 2 - 1 );
// Step 4.3 Reverse the second half of first sub-string
// and first half of second sub-string together
reverse ( str, shift / 2, shift + lenFirst / 2 - 1 );
// Increase the length of first subarray
shift += lenFirst;
}
}
// Driver program to test above function
int main()
{
char str[] = "a1b2c3d4e5f6g7";
moveNumberToSecondHalf( str );
cout<<str;
return 0;
}
// This is code is contributed by rathbhupendra
Java
// Java implementation of above approach
import java.util.*;
class GFG{
static char []str;
// A utility function to reverse
// String str[low..high]
static void reverse(int low, int high)
{
while (low < high)
{
char t = str[low];
str[low] = str[high];
str[high] = t;
++low;
--high;
}
}
// Cycle leader algorithm to move all even
// positioned elements at the end.
static void cycleLeader(int shift, int len)
{
int j;
char item;
for(int i = 1; i < len; i *= 3)
{
j = i;
item = str[j + shift];
do
{
// odd index
if (j % 2 == 1)
j = len / 2 + j / 2;
// even index
else
j /= 2;
// Keep the back-up of element at
// new position
char t = str[j + shift];
str[j + shift] = item;
item = t;
}
while (j != i);
}
}
// The main function to transform a String.
// This function mainly uses cycleLeader()
// to transform
static void moveNumberToSecondHalf()
{
int k, lenFirst;
int lenRemaining = str.length;
int shift = 0;
while (lenRemaining > 0)
{
k = 0;
// Step 1: Find the largest prefix
// subarray of the form 3^k + 1
while (Math.pow(3, k) + 1 <= lenRemaining)
k++;
lenFirst = (int)Math.pow(3, k - 1) + 1;
lenRemaining -= lenFirst;
// Step 2: Apply cycle leader algorithm
// for the largest subarrau
cycleLeader(shift, lenFirst);
// Step 4.1: Reverse the second half
// of first subarray
reverse(shift / 2, shift - 1);
// Step 4.2: Reverse the first half
// of second sub-String.
reverse(shift, shift + lenFirst / 2 - 1);
// Step 4.3 Reverse the second half
// of first sub-String and first half
// of second sub-String together
reverse(shift / 2, shift + lenFirst / 2 - 1);
// Increase the length of first subarray
shift += lenFirst;
}
}
// Driver code
public static void main(String[] args)
{
String st = "a1b2c3d4e5f6g7";
str = st.toCharArray();
moveNumberToSecondHalf();
System.out.print(str);
}
}
// This code is contributed by Princi Singh
Python3
# Python implementation of above approach
# A utility function to reverse string str[low..high]
def Reverse(string: list, low: int, high: int):
while low < high:
string[low], string[high] = string[high], string[low]
low += 1
high -= 1
# Cycle leader algorithm to move all even
# positioned elements at the end.
def cycleLeader(string: list, shift: int, len: int):
i = 1
while i < len:
j = i
item = string[j + shift]
while True:
# odd index
if j & 1:
j = len // 2 + j // 2
# even index
else:
j //= 2
# keep the back-up of element at new position
string[j + shift], item = item, string[j + shift]
if j == i:
break
i *= 3
# The main function to transform a string. This function
# mainly uses cycleLeader() to transform
def moveNumberToSecondHalf(string: list):
k, lenFirst = 0, 0
lenRemaining = len(string)
shift = 0
while lenRemaining:
k = 0
# Step 1: Find the largest prefix
# subarray of the form 3^k + 1
while pow(3, k) + 1 <= lenRemaining:
k += 1
lenFirst = pow(3, k - 1) + 1
lenRemaining -= lenFirst
# Step 2: Apply cycle leader algorithm
# for the largest subarrau
cycleLeader(string, shift, lenFirst)
# Step 4.1: Reverse the second half of first subarray
Reverse(string, shift // 2, shift - 1)
# Step 4.2: Reverse the first half of second sub-string
Reverse(string, shift, shift + lenFirst // 2 - 1)
# Step 4.3 Reverse the second half of first sub-string
# and first half of second sub-string together
Reverse(string, shift // 2, shift + lenFirst // 2 - 1)
# Increase the length of first subarray
shift += lenFirst
# Driver Code
if __name__ == "__main__":
string = "a1b2c3d4e5f6g7"
string = list(string)
moveNumberToSecondHalf(string)
print(''.join(string))
# This code is contributed by
# sanjeev2552
C#
// C# implementation of
// the above approach
using System;
class GFG{
static char []str;
// A utility function to
// reverse String str[low
// ..high]
static void reverse(int low,
int high)
{
while (low < high)
{
char t = str[low];
str[low] = str[high];
str[high] = t;
++low;
--high;
}
}
// Cycle leader algorithm to
// move all even positioned
// elements at the end.
static void cycleLeader(int shift,
int len)
{
int j;
char item;
for(int i = 1;
i < len; i *= 3)
{
j = i;
item = str[j + shift];
do
{
// odd index
if (j % 2 == 1)
j = len / 2 + j / 2;
// even index
else
j /= 2;
// Keep the back-up of
// element at new position
char t = str[j + shift];
str[j + shift] = item;
item = t;
}
while (j != i);
}
}
// The main function to transform
// a String. This function mainly
// uses cycleLeader() to transform
static void moveNumberToSecondHalf()
{
int k, lenFirst;
int lenRemaining = str.Length;
int shift = 0;
while (lenRemaining > 0)
{
k = 0;
// Step 1: Find the largest prefix
// subarray of the form 3^k + 1
while (Math.Pow(3, k) +
1 <= lenRemaining)
k++;
lenFirst = (int)Math.Pow(3,
k - 1) + 1;
lenRemaining -= lenFirst;
// Step 2: Apply cycle leader
// algorithm for the largest
// subarrau
cycleLeader(shift, lenFirst);
// Step 4.1: Reverse the second
// half of first subarray
reverse(shift / 2,
shift - 1);
// Step 4.2: Reverse the
// first half of second
// sub-String.
reverse(shift, shift +
lenFirst / 2 - 1);
// Step 4.3 Reverse the second
// half of first sub-String and
// first half of second sub-String
// together
reverse(shift / 2, shift +
lenFirst / 2 - 1);
// Increase the length of
// first subarray
shift += lenFirst;
}
}
// Driver code
public static void Main(String[] args)
{
String st = "a1b2c3d4e5f6g7";
str = st.ToCharArray();
moveNumberToSecondHalf();
Console.Write(str);
}
}
// This code is contributed by 29AjayKumar
Javascript
<script>
// Javascript implementation of above approach
let str;
// A utility function to reverse
// String str[low..high]
function reverse(low,high)
{
while (low < high)
{
let t = str[low];
str[low] = str[high];
str[high] = t;
++low;
--high;
}
}
// Cycle leader algorithm to move all even
// positioned elements at the end.
function cycleLeader(shift,len)
{
let j;
let item;
for(let i = 1; i < len; i *= 3)
{
j = i;
item = str[j + shift];
do
{
// odd index
if (j % 2 == 1)
j = Math.floor(len / 2) + Math.floor(j / 2);
// even index
else
j =Math.floor(j/2);
// Keep the back-up of element at
// new position
let t = str[j + shift];
str[j + shift] = item;
item = t;
}
while (j != i);
}
}
// The main function to transform a String.
// This function mainly uses cycleLeader()
// to transform
function moveNumberToSecondHalf()
{
let k, lenFirst;
let lenRemaining = str.length;
let shift = 0;
while (lenRemaining > 0)
{
k = 0;
// Step 1: Find the largest prefix
// subarray of the form 3^k + 1
while (Math.pow(3, k) + 1 <= lenRemaining)
k++;
lenFirst = Math.floor(Math.pow(3, k - 1)) + 1;
lenRemaining -= lenFirst;
// Step 2: Apply cycle leader algorithm
// for the largest subarrau
cycleLeader(shift, lenFirst);
// Step 4.1: Reverse the second half
// of first subarray
reverse(Math.floor(shift / 2), shift - 1);
// Step 4.2: Reverse the first half
// of second sub-String.
reverse(shift, shift + Math.floor(lenFirst / 2) - 1);
// Step 4.3 Reverse the second half
// of first sub-String and first half
// of second sub-String together
reverse(Math.floor(shift / 2), shift + Math.floor(lenFirst / 2) - 1);
// Increase the length of first subarray
shift += lenFirst;
}
}
// Driver code
let st = "a1b2c3d4e5f6g7";
str = st.split("");
moveNumberToSecondHalf();
document.write(str.join(""));
// This code is contributed by rag2127
</script>
abcdefg1234567
Complejidad temporal: O(n 2 )
Espacio auxiliar: O(1)
Haga clic aquí para ver varios casos de prueba.
Notas:
- Si el tamaño de la array ya tiene la forma 3^k + 1, podemos aplicar directamente el algoritmo de iteración del líder del ciclo. No hay necesidad de unirse.
- El algoritmo de iteración del líder del ciclo solo es aplicable a arrays de tamaño de la forma 3^k + 1.
¿Cómo es la complejidad del tiempo O(n)?
Cada artículo en un ciclo se desplaza como máximo una vez. Por lo tanto, la complejidad temporal del algoritmo del líder del ciclo es O(n). La complejidad temporal de la operación inversa es O(n). Pronto actualizaremos la prueba matemática de la complejidad temporal del algoritmo.
Ejercicio:
Dada la string en la forma «abcdefg1234567», conviértala a «a1b2c3d4e5f6g7» en el lugar y en complejidad de tiempo O(n).
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