编写一个函数rotate（ar[]，d，n），将大小为n的arr[]旋转d个元素。
null
将上述阵列旋转2将生成阵列
方法1（使用临时数组）
Input arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2, n =7 1) 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]
C++
// C++ program to rotate an array by // d elements #include <bits/stdc++.h> using namespace std; int main(){ int a[]={1,2,3,4,5,6,7,8,9}; int n=9; int d=2; int temp[d]; for ( int i=0;i<d;i++){ temp[i]=a[i]; } for ( int i=0,j=d;i<n-1;i++,j++){ a[i]=a[j]; } int c[n+d]; int i=0; int j=0; int k=0; for (;i<n-2;i++){ c[k++]=a[i]; } for (;j<d;j++){ c[k++]=temp[j]; } for ( int i=0;i<n;i++){ cout<<c[i]<< " " ; } } |
输出：
345678912
时间复杂性： O（n） 辅助空间： O（d）
方法2（逐个旋转）
leftRotate(arr[], d, n)
start
For i = 0 to i < d
Left rotate all elements of arr[] by one
end
要按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]。
C++
// C++ program to rotate an array by // d elements #include <bits/stdc++.h> using namespace std; /*Function to left Rotate arr[] of size n by 1*/ void leftRotatebyOne( int arr[], int n) { int temp = arr[0]; int i; for (i = 0; i < n-1; i++) arr[i] = arr[i+1]; arr[i] = temp; } /*Function to left rotate arr[] of size n by d*/ void leftRotate( int arr[], int d, int n) { for ( int i = 0; i < d; i++) leftRotatebyOne(arr, n); } /* utility function to print an array */ void printArray( int arr[], int size) { for ( int i = 0; i < size; i++) cout << arr[i] << " " ; } /* Driver program to test above functions */ int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7}; int n = sizeof (arr) / sizeof (arr[0]); // Function calling leftRotate(arr, 2, n); printArray(arr, n); return 0; } |
C
/*Function to left Rotate arr[] of size n by 1*/ void leftRotatebyOne( int arr[], int n); /*Function to left rotate arr[] of size n by d*/ void leftRotate( int arr[], int d, int n) { int i; for (i = 0; i < d; i++) leftRotatebyOne(arr, n); } void leftRotatebyOne( int arr[], int n) { int i, temp; temp = arr[0]; for (i = 0; i < n-1; i++) arr[i] = arr[i+1]; arr[i] = temp; } /* utility function to print an array */ void printArray( int arr[], int size) { int i; for (i = 0; i < size; i++) printf ( "%d " , arr[i]); } /* Driver program to test above functions */ int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7}; leftRotate(arr, 2, 7); printArray(arr, 7); getchar (); return 0; } |
C#
// C# program for array rotation using System; class GFG { /* Function to left rotate arr[] of size n by d*/ static void leftRotate( int []arr, int d, int n) { for ( int i = 0; i < d; i++) leftRotatebyOne(arr, n); } static void leftRotatebyOne( int []arr, int n) { int i, temp = arr[0]; for (i = 0; i < n - 1; i++) arr[i] = arr[i + 1]; arr[i] = temp; } /* utility function to print an array */ static void printArray( int []arr, int size) { for ( int i = 0; i < size; i++) Console.Write(arr[i] + " " ); } // Driver code public static void Main() { int []arr = {1, 2, 3, 4, 5, 6, 7}; leftRotate(arr, 2, 7); printArray(arr, 7); } } // This code is contributed by Sam007 |
输出：
3 4 5 6 7 1 2
输出：
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，让arr[]为{1,2,3,4,5,6,7,8,9,10,11,12}
a） 元素首先在第一组中移动—— （请参见下图了解该运动） ![图片[3]-数组旋转程序的C程序-yiteyi-C++库](https://media.geeksforgeeks.org/wp-content/uploads/arra.jpg)
arr[]在这一步之后–>{4 2 3 7 5 6 10 8 9 1 11 12}
b） 第二盘。 arr[]在这一步之后–{4 5 3 7 8 6 10 11 9 1 2}
c） 最后进入第三盘。 arr[]在这一步之后–>{4 5 6 7 8 9 10 11 12 1 2 3}
C++
// C++ program to rotate an array by // d elements #include <bits/stdc++.h> using namespace std; /*Function to get gcd of a and b*/ int gcd( int a, int b) { if (b == 0) return a; else return gcd(b, a%b); } /*Function to left rotate arr[] of siz n by d*/ void leftRotate( int arr[], int d, int n) { for ( int i = 0; i < gcd(d, n); i++) { /* move i-th values of blocks */ int temp = arr[i]; int j = i; while (1) { int k = j + d; if (k >= n) k = k - n; if (k == i) break ; arr[j] = arr[k]; j = k; } arr[j] = temp; } } // Function to print an array void printArray( int arr[], int size) { for ( int i = 0; i < size; i++) cout << arr[i] << " " ; } /* Driver program to test above functions */ int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7}; int n = sizeof (arr) / sizeof (arr[0]); // Function calling leftRotate(arr, 2, n); printArray(arr, n); return 0; } |
C
/* function to print an array */ void printArray( int arr[], int size); /*Function to get gcd of a and b*/ int gcd( int a, int b); /*Function to left rotate arr[] of siz n by d*/ void leftRotate( int arr[], int d, int n) { int i, j, k, temp; for (i = 0; i < gcd(d, n); i++) { /* 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 */ void printArray( int arr[], int size) { int i; for (i = 0; i < size; i++) printf ( "%d " , arr[i]); } /*Function to get gcd of a and b*/ int gcd( int a, int b) { if (b==0) return a; else return gcd(b, a%b); } /* Driver program to test above functions */ int main() { int arr[] = {1, 2, 3, 4, 5, 6, 7}; leftRotate(arr, 2, 7); printArray(arr, 7); getchar (); return 0; } |
C#
// C# program for array rotation using System; class GFG { /* Function to left rotate arr[] of size n by d*/ static void leftRotate( int []arr, int d, int n) { int i, j, k, temp; for (i = 0; i < gcd(d, n); i++) { /* move i-th values of blocks */ temp = arr[i]; j = i; while ( true ) { 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 */ static void printArray( int []arr, int size) { for ( int i = 0; i < size; i++) Console.Write(arr[i] + " " ); } /* Function to get gcd of a and b*/ static int gcd( int a, int b) { if (b == 0) return a; else return gcd(b, a % b); } // Driver code public static void Main() { int []arr = {1, 2, 3, 4, 5, 6, 7}; leftRotate(arr, 2, 7); printArray(arr, 7); } } // This code is contributed by Sam007 |
输出：
3 4 5 6 7 1 2
输出：
3 4 5 6 7 1 2
时间复杂性： O（n） 辅助空间： O（1） 请参阅完整的文章 阵列旋转程序 更多细节！
© 版权声明
文章版权归作者所有，未经允许请勿转载。
THE END
![关于”PostgreSQL错误：关系[表]不存在“问题的原因和解决方案-yiteyi-C++库](https://www.yiteyi.com/wp-content/themes/zibll/img/thumbnail.svg)
