【算法】数组左旋 字符串左旋

什么是数组左旋？

数组左旋就是，对给定的n个元素的数组，向左旋转移动d个元素，例如

左旋2个元素，得到

方法一：使用临时数组

时间复杂度:O(n)

空间复杂度:O(d)

public static void solution1(int[] array1, int d){int[] temp = new int[d];for (int i = 0; i < array1.length; i++){if (i < d){temp[i] = array1[i];} else {array1[i-d] = array1[i];}}int j = 0;for (int i = array1.length - d; i < array1.length; i++){array1[i] = temp[j++];}for (int i = 0; i < array1.length; i++){System.out.println(array1[i]);}}

方法二：依次进行数组左旋

时间复杂度:O(n * d)

空间复杂度:O(1)

// Java program to rotate an array by// d elementsclass RotateArray {/*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);}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[n-1] = temp;}/* utility function to print an array */void printArray(int arr[], int n){for (int i = 0; i < n; i++)System.out.print(arr[i] + " ");}// Driver program to test above functionspublic static void main(String[] args){RotateArray rotate = new RotateArray();int arr[] = { 1, 2, 3, 4, 5, 6, 7 };rotate.leftRotate(arr, 2, 7);rotate.printArray(arr, 7);}}

d等于几，就相当于做几次数组元素的移动

方法三：分组左旋法

时间复杂度:O(n)

空间复杂度:O(1)

// Java program to rotate an array by// d elementsclass RotateArray {/*Function to left rotate arr[] of siz n by d*/void leftRotate(int arr[], int d, int n){/* To handle if d >= n */d = d % n;int i, j, k, temp;int g_c_d = gcd(d, n);for (i = 0; i < g_c_d; 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 */void printArray(int arr[], int size){int i;for (i = 0; i < size; i++)System.out.print(arr[i] + " ");}/*Fuction to get gcd of a and b*/int gcd(int a, int b){if (b == 0)return a;elsereturn gcd(b, a % b);}// Driver program to test above functionspublic static void main(String[] args){RotateArray rotate = new RotateArray();int arr[] = { 1, 2, 3, 4, 5, 6, 7 };rotate.leftRotate(arr, 2, 7);rotate.printArray(arr, 7);}}

说明：

1. 根据数组的长度n和左旋的大小d计算最大公约数，例如n=12, d=3, 则最大公约数为3

2. 根据最大公约数，对元素进行分组，则分为4组。{1，2，3} {4, 5, 6} {7, 8, 9} {10, 11, 12}

3. 依次对每组的第1个元素、第2个元素，。。第gcd个元素进行大小为d的左旋

对1，4，7，10的左旋，我们得到

{4 2 3 7 5 6 10 8 9 1 11 12}

再对2，5，8，11的左旋，我们得到

{4 5 3 7 8 6 10 11 9 1 2 12}

再对3，5，8，12的左旋，我们得到

{4 5 6 7 8 9 10 11 12 1 2 3}

如此，便得到最终的结果。

方法三：逆转字符串

根据左旋的个数，将字符串进行分组。例如，源字符串为“abcdefg”, 左旋2个字符，则分组为

“ab” “cdefg”

接着，对各自的分组进行逆转：

“ba” “gfedc”

接着拼装起来

“bagfedc”

对拼装后的字符串逆转

“cdefgab”

如果觉得《【算法】数组左旋 字符串左旋》对你有帮助，请点赞、收藏，并留下你的观点哦！