Рубрики

Алгоритм на месте для преобразования строки

Получив строку, переместите все четные элементы в конец строки. При перемещении элементов сохраняйте относительный порядок всех элементов с четным и нечетным расположением. Например, если заданная строка «a1b2c3d4e5f6g7h8i9j1k2l3m4», преобразуйте ее в «abcdefghijklm1234567891234» на месте и с O (n) сложностью по времени.

Ниже приведены шаги:

1. Вырежьте наибольшую префиксную подстроку размером 3 ^ k + 1. На этом шаге мы найдем наибольшее неотрицательное целое число k такое, что 3 ^ k + 1 меньше или равно n (длина строки)

2. Примените алгоритм итерации лидера цикла (он обсуждался ниже), начиная с индекса 1, 3, 9 …… к этой подстроке. Алгоритм итерации лидера цикла перемещает все элементы этой подстроки в их правильные позиции, то есть все алфавиты смещаются в левую половину подстроки, а все цифры смещаются в правую половину этой подстроки.

3. Обработайте оставшуюся подстроку рекурсивно, используя шаги # 1 и # 2.

4. Теперь нам нужно только объединить обработанные подстроки. Начните с любого конца (скажем, слева), выберите две подстроки и примените следующие шаги:

…. 4.1. Переверните вторую половину первой подстроки.
…. 4.2. Перевернуть первую половину второй подстроки.
…. 4.3. Переверните вторую половину первой подстроки и первую половину второй подстроки вместе.

5. Повторяйте шаг № 4, пока все подстроки не будут объединены. Это похоже на k-way слияние, когда первая подстрока соединяется со второй. Результирующий объединяется с третьим и так далее.

Позвольте нам понять это на примере:

Обратите внимание, что мы использовали такие значения, как 10, 11 12 в приведенном ниже примере. Рассматривайте эти значения только как отдельные символы. Эти значения используются для лучшей читаемости.

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

После разбиения на размер формы 3 ^ k + 1 формируются две подстроки размером 10 каждая. Третья подстрока образована размером 4, а четвертая подстрока сформирована размером 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

После применения итерационного алгоритма лидера цикла к первой подстроке:

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

После применения итерационного алгоритма лидера цикла ко второй подстроке:

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

После применения итерационного алгоритма лидера цикла к третьей подстроке:

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

После применения итерационного алгоритма лидера цикла к четвертой подстроке:

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

Соединение первой подстроки и второй подстроки:
1. Вторая половина первой подстроки и первая половина второй подстроки перевернуты.

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. Вторая половина первой подстроки и первая половина второй подстроки перевернуты вместе (они объединены, т. Е. Теперь есть только три подстроки).

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

Соединение первой подстроки и второй подстроки:
1. Вторая половина первой подстроки и первая половина второй подстроки перевернуты.

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. Вторая половина первой подстроки и первая половина второй подстроки перевернуты вместе (они объединены, то есть теперь есть только две подстроки).

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 

Соединение первой подстроки и второй подстроки:
1. Вторая половина первой подстроки и первая половина второй подстроки перевернуты.

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. Вторая половина первой подстроки и первая половина второй подстроки перевернуты вместе (они объединены, т.е. теперь есть только одна подстрока).

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

Поскольку все подстроки были объединены, мы закончили.

Как работает алгоритм итерации лидера цикла?

Позвольте нам понять это на примере:

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

Пусть len будет длиной строки. Если мы внимательно наблюдаем, мы находим, что новый индекс дается формулой ниже:

if( oldIndex is odd )
    newIndex = len / 2 + oldIndex / 2;
else
        newIndex = oldIndex / 2;

Таким образом, проблема сводится к смещению элементов к новым индексам на основе приведенной выше формулы.

Будет использован алгоритм итерации лидера цикла, начиная с индексов вида 3 ^ k, начиная с k = 0.

Ниже приведены шаги:

1. Найти новую позицию для позиции в позиции i. Прежде чем поместить этот элемент в новую позицию, сохраните резервную копию элемента в новой позиции. Теперь поместите предмет на новую позицию.

2. Повторите шаг # 1 для новой позиции, пока цикл не будет завершен, т.е. пока процедура не вернется в исходную позицию.

3. Примените алгоритм итерации лидера цикла к следующему индексу вида 3 ^ k. Повторяйте этот шаг, пока 3 ^ k <len.

Рассмотрим входной массив размером 28:

Первая итерация лидера цикла, начиная с индекса 1:

1-> 14-> 7-> 17-> 22-> 11-> 19-> 23-> 25-> 26-> 13-> 20-> 10-> 5-> 16-> 8-> 4- > 2-> 1

Вторая итерация лидера цикла, начиная с индекса 3:

3-> 15-> 21-> 24-> 12-> 6-> 3

Третья итерация лидера цикла, начиная с индекса 9:

9-> 18-> 9

На основе приведенного выше алгоритма ниже приведен код:

C ++

// C ++ реализация вышеуказанного подхода
#include <bits/stdc++.h>

using namespace std;

  
// Утилита для обмена символами

void swap ( char* a, char* b ) 

    char t = *a; 

    *a = *b; 

    *b = t; 

  
// Вспомогательная функция для обращения строки str [low..high]

void reverse ( char* str, int low, int high ) 

    while ( low < high ) 

    

        swap( &str[low], &str[high] ); 

        ++low; 

        --high; 

    

  
// алгоритм лидера цикла, чтобы переместить все
// позиционируемые элементы в конце.

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

        

            // нечетный индекс

            if ( j & 1 ) 

                j = len / 2 + j / 2; 

            // четный индекс

            else

                j /= 2; 

  

            // сохранить резервную копию элемента в новой позиции

            swap (&str[j + shift], &item); 

        

        while ( j != i ); 

    

  
// Основная функция для преобразования строки. Эта функция
// в основном использует циклLeader () для преобразования

void moveNumberToSecondHalf( char* str ) 

    int k, lenFirst; 

  

    int lenRemaining = strlen( str ); 

    int shift = 0; 

  

    while ( lenRemaining ) 

    

        k = 0; 

  

        // Шаг 1: Найти самый большой префикс

        // подрешетка вида 3 ^ k + 1

        while ( pow( 3, k ) + 1 <= lenRemaining ) 

            k++; 

        lenFirst = pow( 3, k - 1 ) + 1; 

        lenRemaining -= lenFirst; 

  

        // Шаг 2: применить алгоритм лидера цикла

        // для самого большого субаррау

        cycleLeader ( str, shift, lenFirst ); 

  

        // Шаг 4.1: перевернуть вторую половину первого подмассива

        reverse ( str, shift / 2, shift - 1 ); 

  

        // Шаг 4.2: перевернуть первую половину второй подстроки.

        reverse ( str, shift, shift + lenFirst / 2 - 1 ); 

  

        // Шаг 4.3 Перевернуть вторую половину первой подстроки

        // и первая половина второй подстроки вместе

        reverse ( str, shift / 2, shift + lenFirst / 2 - 1 ); 

  

        // Увеличить длину первого подмассива

        shift += lenFirst; 

    

  
// Программа драйвера для проверки вышеуказанной функции

int main() 

    char str[] = "a1b2c3d4e5f6g7"

    moveNumberToSecondHalf( str ); 

    cout<<str; 

    return 0; 

  
// Это код, предоставленный rathbhupendra

С

#include <stdio.h>
#include <string.h>
#include <math.h>

  
// Утилита для обмена символами

void swap ( char* a, char* b )

{

    char t = *a;

    *a = *b;

    *b = t;

}

  
// Вспомогательная функция для обращения строки str [low..high]

void reverse ( char* str, int low, int high )

{

    while ( low < high )

    {

        swap( &str[low], &str[high] );

        ++low;

        --high;

    }

}

  
// алгоритм лидера цикла для перемещения всех четных элементов
// в конце.

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

        {

            // нечетный индекс

            if ( j & 1 )

                j = len / 2 + j / 2;

            // четный индекс

            else

                j /= 2;

  

            // сохранить резервную копию элемента в новой позиции

            swap (&str[j + shift], &item);

        }

        while ( j != i );

    }

}

  
// Основная функция для преобразования строки. Эта функция в основном использует
// cycleLeader () для преобразования

void moveNumberToSecondHalf( char* str )

{

    int k, lenFirst;

  

    int lenRemaining = strlen( str );

    int shift = 0;

  

    while ( lenRemaining )

    {

        k = 0;

  

        // Шаг 1: Найти самый большой префиксный подмассив вида 3 ^ k + 1

        while ( pow( 3, k ) + 1 <= lenRemaining )

            k++;

        lenFirst = pow( 3, k - 1 ) + 1;

        lenRemaining -= lenFirst;

  

        // Шаг 2: Применить алгоритм лидера цикла для самого большого субаррау

        cycleLeader ( str, shift, lenFirst );

  

        // Шаг 4.1: перевернуть вторую половину первого подмассива

        reverse ( str, shift / 2, shift - 1 );

  

        // Шаг 4.2: перевернуть первую половину второй подстроки.

        reverse ( str, shift, shift + lenFirst / 2 - 1 );

  

        // Шаг 4.3 Перевернуть вторую половину первой подстроки и первую

        // половина второй подстроки вместе

        reverse ( str, shift / 2, shift + lenFirst / 2 - 1 );

  

        // Увеличить длину первого подмассива

        shift += lenFirst;

    }

}

  
// Программа драйвера для проверки вышеуказанной функции

int main()

{

    char str[] = "a1b2c3d4e5f6g7";

    moveNumberToSecondHalf( str );

    printf( "%s", str );

    return 0;

}


Выход:

abcdefg1234567

Нажмите здесь, чтобы увидеть различные тесты.

Примечания:
1. Если размер массива уже находится в форме 3 ^ k + 1, мы можем напрямую применить алгоритм итерации лидера цикла. Нет необходимости присоединяться.

2. Алгоритм итерации лидера цикла применим только к массивам размером 3 ^ k + 1.

Как сложность времени O (n)?
Каждый элемент в цикле сдвигается не более одного раза. Таким образом, временная сложность алгоритма лидера цикла составляет O (n). Временная сложность обратной операции составляет O (n). Мы скоро обновим математическое доказательство временной сложности алгоритма.

Упражнение:
Получив строку в форме «abcdefg1234567», конвертируйте ее в «a1b2c3d4e5f6g7» на месте и за O (n) сложность времени.

Ссылки:
Простой на месте алгоритм для In-Shu? E.

___ Аашиш Барнвал. Пожалуйста, напишите комментарии, если вы обнаружите что-то неправильное или хотите поделиться дополнительной информацией по обсуждаемой выше теме.

Рекомендуемые посты:

Алгоритм на месте для преобразования строки

0.00 (0%) 0 votes