数组旋转的Python程序-yiteyi-C++库

编写一个函数rotate（ar[]，d，n），将大小为n的arr[]旋转d个元素。

null

Array

将上述阵列旋转2将生成阵列

ArrayRotation1

方法1（使用临时数组） :

Input arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2, n =71) Store d elements in a temp array   temp[] = [1, 2]2) Shift rest of the arr[]   arr[] = [3, 4, 5, 6, 7, 6, 7]3) Store back the d elements   arr[] = [3, 4, 5, 6, 7, 1, 2]

Python3

                         # function to rotate array by d elements using temp array                       
                         def                                     rotateArray(arr, n, d):                       
                                                 temp                                     =                                     []                       
                                                 i                                     =                                     0                       
                                                 while                                     (i < d):                       
                                                 temp.append(arr[i])                       
                                                 i                                     =                                     i                                     +                                     1                       
                                                 i                                     =                                     0                       
                                                 while                                     (d < n):                       
                                                 arr[i]                                     =                                     arr[d]                       
                                                 i                                     =                                     i                                     +                                     1                       
                                                 d                                     =                                     d                                     +                                     1                       
                                                 arr[:]                                     =                                     arr[: i]                                     +                                     temp                       
                                                 return                                     arr                       
           
           
                         # Driver function to test above function                       
                         arr                                     =                                     [                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     ,                                     6                                     ,                                     7                                     ]                       
                         print                                     (                                     "Array after left rotation is: "                                     , end                                     =                                     ' '                                     )                       
                         print                                     (rotateArray(arr,                                     len                                     (arr),                                     2                                     ))                       
           
                         # this code is contributed by Anabhra Tyagi                       

输出

Array after left rotation is:  [3, 4, 5, 6, 7, 1, 2]

时间复杂性： O（n） 辅助空间： O（d）

方法2（逐个旋转） :

leftRotate(arr[], d, n)start  For i = 0 to i < d    Left rotate all elements of arr[] by oneend

要按1旋转，将arr[0]存储在临时变量temp中，将arr[1]移动到arr[0]，将arr[2]移动到arr[1]……最后将temp移动到arr[n-1] 让我们以同样的例子arr[]=[1,2,3,4,5,6,7]，d=2 将arr[]旋转2次我们在第一次旋转后得到[2,3,4,5,6,7,1]，在第二次旋转后得到[3,4,5,6,7,1,2]。

Python3

                         #Function to left rotate arr[] of size n by d*/                       
                         def                                     leftRotate(arr, d, n):                       
                                                 for                                     i                                     in                                     range                                     (d):                       
                                                 leftRotatebyOne(arr, n)                       
           
                         #Function to left Rotate arr[] of size n by 1*/                       
                         def                                     leftRotatebyOne(arr, n):                       
                                                 temp                                     =                                     arr[                                     0                                     ]                       
                                                 for                                     i                                     in                                     range                                     (n                                     -                                     1                                     ):                       
                                                 arr[i]                                     =                                     arr[i                                     +                                     1                                     ]                       
                                                 arr[n                                     -                                     1                                     ]                                     =                                     temp                       
                                   
           
                         # utility function to print an array */                       
                         def                                     printArray(arr,size):                       
                                                 for                                     i                                     in                                     range                                     (size):                       
                                                 print                                     (                                     "%d"                                     %                                     arr[i],end                                     =                                     " "                                     )                       
           
                                   
                         # Driver program to test above functions */                       
                         arr                                     =                                     [                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     ,                                     6                                     ,                                     7                                     ]                       
                         leftRotate(arr,                                     2                                     ,                                     7                                     )                       
                         printArray(arr,                                     7                                     )                       
           
                         # This code is contributed by Shreyanshi Arun                       

输出

3 4 5 6 7 1 2

时间复杂性： O（n*d） 辅助空间： O（1）

方法3（杂耍算法） 这是方法2的扩展。不要逐个移动，而是将数组分成不同的集合其中集合数等于n和d的GCD，并在集合内移动元素。如果GCD与上述示例数组（n=7，d=2）一样为1，那么元素将仅在一个集合内移动，我们只需从temp=arr[0]开始，并将arr[I+d]移动到arr[I]，最后将temp存储在正确的位置。下面是一个n=12和d=3的例子。GCD为3分

Let arr[] be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}a)    Elements are first moved in first set – (See below diagram for this movement

ArrayRotation

          arr[] after this step --> {4 2 3 7 5 6 10 8 9 1 11 12}b)    Then in second set.          arr[] after this step --> {4 5 3 7 8 6 10 11 9 1 2 12}c)    Finally in third set.          arr[] after this step --> {4 5 6 7 8 9 10 11 12 1 2 3}

Python3

                         #Function to left rotate arr[] of size n by d                       
                         def                                     leftRotate(arr, d, n):                       
                                                 for                                     i                                     in                                     range                                     (gcd(d,n)):                       
                                   
                                                 # move i-th values of blocks                       
                                                 temp                                     =                                     arr[i]                       
                                                 j                                     =                                     i                       
                                                 while                                     1                                     :                       
                                                 k                                     =                                     j                                     +                                     d                       
                                                 if                                     k >                                     =                                     n:                       
                                                 k                                     =                                     k                                     -                                     n                       
                                                 if                                     k                                     =                                     =                                     i:                       
                                                 break                       
                                                 arr[j]                                     =                                     arr[k]                       
                                                 j                                     =                                     k                       
                                                 arr[j]                                     =                                     temp                       
           
                         #UTILITY FUNCTIONS                       
                         #function to print an array                       
                         def                                     printArray(arr, size):                       
                                                 for                                     i                                     in                                     range                                     (size):                       
                                                 print                                     (                                     "%d"                                     %                                     arr[i], end                                     =                                     " "                                     )                       
                                   
                         #Function to get gcd of a and b                       
                         def                                     gcd(a, b):                       
                                                 if                                     b                                     =                                     =                                     0                                     :                       
                                                 return                                     a;                       
                                                 else                                     :                       
                                                 return                                     gcd(b, a                                     %                                     b)                       
                                   
                         # Driver program to test above functions                       
                         arr                                     =                                     [                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     ,                                     6                                     ,                                     7                                     ]                       
                         leftRotate(arr,                                     2                                     ,                                     7                                     )                       
                         printArray(arr,                                     7                                     )                       
           
                         # This code is contributed by Shreyanshi Arun                       

输出

3 4 5 6 7 1 2

时间复杂性： O（n） 辅助空间： O（1）

另一种方法： 使用列表切片

Python3

                         # Python program using the List                       
                         # slicing approach to rotate the array                       
                         def                                     rotateList(arr,d,n):                       
                                                 arr[:]                                     =                                     arr[d:n]                                     +                                     arr[                                     0                                     :d]                       
                                                 return                                     arr                       
                         # Driver function to test above function                       
                         arr                                     =                                     [                                     1                                     ,                                     2                                     ,                                     3                                     ,                                     4                                     ,                                     5                                     ,                                     6                                     ]                       
                         print                                     (arr)                       
                         print                                     (                                     "Rotated list is"                                     )                       
                         print                                     (rotateList(arr,                                     2                                     ,                                     len                                     (arr)))                       
           
                         # this code is contributed by virusbuddah                       

输出

[1, 2, 3, 4, 5, 6]Rotated list is[3, 4, 5, 6, 1, 2]

如果阵列需要旋转超过其长度，则应进行mod。

例如：将大小为n的arr[]旋转d，其中d大于n。在这种情况下，应计算d%n，并根据mod后的结果旋转。请参阅完整的文章阵列旋转程序更多细节！

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章