算法：如何实现字符串转换的就地算法？

本文概述

• C ++
• C
• Python3

给定字符串, 将所有偶数定位的元素移到字符串末尾。移动元素时, 请保持所有偶数和奇数元素的相对顺序相同。例如, 如果给定的字符串是" a1b2c3d4e5f6g7h8i9j1k2l3m4", 则将其就地转换为" abcdefghijklm1234567891234", 并且时间复杂度为O(n)。

步骤如下：

1.切出大小为3 ^ k + 1的最大前缀子字符串。在此步骤中, 我们找到最大的非负整数k, 使得3 ^ k + 1小于或等于n(字符串的长度) )

2.应用从索引1、3、9…开始的循环领导者迭代算法(在下面进行讨论)到该子字符串。循环领导迭代算法将这个子字符串的所有项目移动到它们的正确位置, 即所有字母都移到该子字符串的左半部分, 而所有数字都移到该子字符串的右半部分。

3.使用步骤1和2递归处理其余子字符串。

4.现在, 我们只需要将处理后的子字符串连接在一起。从任意一端开始(例如, 从left开始), 选择两个子字符串, 然后执行以下步骤：

…。

4.1

反转第一个子字符串的后半部分。

…。

4.2

反转第二个子字符串的前半部分。

…。

4.3

将第一个子字符串的后半部分和第二个子字符串的前半部分一起反转。

5.重复步骤4, 直到所有子字符串都已加入。它类似于k方向合并, 其中第一个子字符串与第二个子字符串连接在一起。结果与第三合并, 依此类推。

让我们通过一个例子来理解它：

请注意, 在下面的示例中, 我们使用了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;

因此, 问题减少到基于上述公式将元素转移到新索引。

循环首长迭代算法将从k = 0的索引形式3 ^ k开始应用。

步骤如下：

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++ implimentation 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

C

#include <stdio.h>
#include <string.h>
#include <math.h>
  
// 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 );
     printf ( "%s" , str );
     return 0;
}

Python3

# Python implimentation 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

输出如下：

abcdefg1234567

请点击这里查看各种测试案例。

笔记：

1.

如果数组大小已经是3 ^ k + 1的形式, 我们可以直接应用循环前导迭代算法。无需加入。

2.Cycle Leader迭代算法仅适用于大小为3 ^ k + 1的数组。

时间复杂度O(n)如何？

一个循环中的每个项目最多只能移动一次。因此, 循环前导算法的时间复杂度为O(n)。反向操作的时间复杂度为O(n)。我们将很快更新算法时间复杂度的数学证明。

行使：

给定形式为" abcdefg1234567"的字符串, 就地将其转换为" a1b2c3d4e5f6g7", 时间复杂度为O(n)。

参考文献：

一种简单的就地安装算法。

__阿什什·巴恩沃尔(Aashish Barnwal)。如果发现任何不正确的地方, 或者想分享有关上述主题的更多信息, 请写评论。