阵列旋转反转算法的Java程序-yiteyi-C++库

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

null

例子：

Input :  arr[] = [1, 2, 3, 4, 5, 6, 7]
         d = 2
Output : arr[] = [3, 4, 5, 6, 7, 1, 2]

Array

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

ArrayRotation1

建议：请在“上解决” 实践 “首先，在讨论解决方案之前。

算法：

rotate(arr[], d, n)
  reverse(arr[], 1, d) ;
  reverse(arr[], d + 1, n);
  reverse(arr[], 1, n);

设AB是输入数组的两部分，其中A=arr[0..d-1]和B=arr[d..n-1]。该算法的思想是：

反转A得到ArB，其中Ar是A的反转。
反转B以获得ArBr，其中Br是B的反转。
全部反转以获得（ArBr）r=BA。

例子： 让数组arr[]=[1,2,3,4,5,6,7]，d=2，n=7 A=[1,2]和B=[3,4,5,6,7]

反过来，我们得到ArB=[2,1,3,4,5,6,7]
反向B，我们得到ArBr=[2,1,7,6,5,4,3]
全部倒转，我们得到（ArBr）r=[3,4,5,6,7,1,2]

下面是上述方法的Java实现：

                       // Java program for reversal algorithm of array rotation                     
                       import                                  java.io.*;                     
                                
                       class                                  LeftRotate {                     
                                             /* Function to left rotate arr[] of size n by d */                     
                                             static                                  void                                  leftRotate(                                  int                                  arr[],                                  int                                  d)                     
                                             {                     
                                             int                                  n = arr.length;                     
                                             rvereseArray(arr,                                  0                                  , d -                                  1                                  );                     
                                             rvereseArray(arr, d, n -                                  1                                  );                     
                                             rvereseArray(arr,                                  0                                  , n -                                  1                                  );                     
                                             }                     
                                
                                             /*Function to reverse arr[] from index start to end*/                     
                                             static                                  void                                  rvereseArray(                                  int                                  arr[],                                  int                                  start,                                  int                                  end)                     
                                             {                     
                                             int                                  temp;                     
                                             while                                  (start < end) {                     
                                             temp = arr[start];                     
                                             arr[start] = arr[end];                     
                                             arr[end] = temp;                     
                                             start++;                     
                                             end--;                     
                                             }                     
                                             }                     
                                
                                             /*UTILITY FUNCTIONS*/                     
                                             /* function to print an array */                     
                                             static                                  void                                  printArray(                                  int                                  arr[])                     
                                             {                     
                                             for                                  (                                  int                                  i =                                  0                                  ; i < arr.length; i++)                     
                                             System.out.print(arr[i] +                                  " "                                  );                     
                                             }                     
                                
                                             /* Driver program to test above functions */                     
                                             public                                  static                                  void                                  main(String[] args)                     
                                             {                     
                                             int                                  arr[] = {                                  1                                  ,                                  2                                  ,                                  3                                  ,                                  4                                  ,                                  5                                  ,                                  6                                  ,                                  7                                  };                     
                                             leftRotate(arr,                                  2                                  );                                  // Rotate array by 2                     
                                             printArray(arr);                     
                                             }                     
                       }                     
                       /*This code is contributed by Devesh Agrawal*/                     

输出：

3 4 5 6 7 1 2

时间复杂性： O（n）

请参阅完整的文章阵列旋转的反转算法更多细节！

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

THE END

技术文章