旋转数组
一文横扫数组基础知识
旋转数组分为左旋转和右旋转两类，力扣 189 题为右旋转的状况，今日分享的为左旋转。
给定一个数组，将数组中的元素向左旋转 k 个地位，其中 k 是非正数。
<p align='center'>图 0-1 数组 arr 左旋转 k=2 个地位</p>
原数组为 arr[] = [1,2,3,4,5,6,7] ，将其向左旋转 2 个元素的地位，失去数组 arr[] = [3,4,5,6,7,1,2]。
举荐大家去做一下力扣 189 题右旋转数组的题目。
办法一（长期数组）
该办法最为简略和直观，例如，对数组 arr[] = [1,2,3,4,5,6,7] ，k = 2 的状况，就是将数组中的前 k 个元素挪动到数组的开端，那么咱们只需利用一个长期的数组 temp[] 将前 k 个元素保存起来 temp[] = [1,2] ，而后将数组中其余元素向左挪动 2 个地位 arr[] = [3,4,5,6,7,6,7] ，最初再将长期数组 temp 中的元素存回原数组，即失去旋转后的数组 arr[] = [3,4,5,6,7,1,2] ，如图 1-1 所示。
<p align='center'>图 1-1 长期数组法</p>
PS：编写代码时留神下标的边界条件。
void rotationArray(int* arr, int k, int n) { int temp[k]; // 长期数组 int i,j; // 1. 保留数组 arr 中的前 k 个元素到长期数组 temp 中 for( i = 0;i < k;i++) { temp[i] = arr[i]; } // 2. 将数组中的其余元素向前挪动k个地位 for( i = 0;i < n-k; i++) { arr[i] = arr[i+k]; } // 3. 将长期数组中的元素存入原数组 for( j = 0; j < k; j++) { arr[i++] = temp[j]; }} 复杂度剖析
- 工夫复杂度：$O(n)$ ，n 示意数组的长度。
- 空间复杂度：$\Theta(k)$ ，k 示意左旋的的地位数。
办法二（循序渐进挪动法）
循序渐进就是依照左旋转的定义一步一步地挪动。
对于第一次旋转，将 arr[0] 保留到一个长期变量 temp 中，而后将 arr[1] 中的元素挪动到 arr[0] ，arr[2] 挪动到 arr[1] 中，...，以此类推，最初将 temp 存入 arr[n-1] 当中。
同样以数组 arr[] = {1,2,3,4,5,6,7} , k = 2 为例，咱们将数组旋转了 2 次
第一次旋转后失去的数组为 arr[] = {2,3,4,5,6,7,1}；
第二次旋转后失去的数组为 arr[] = {3,4,5,6,7,1,2} 。
具体步骤如图 2-1 所示。
<p align='center'>图 2-1 循序渐进左旋法</p>
实现代码
C 语言实现
// c 语言实现，学习算法重要的是思维，实现要求的是根底语法#include<stdio.h>void leftRotate(int[] arr, int k, int n){ int i; for (i = 0; i < k; i++) { leftRotateByOne(arr, n); }}void leftRotateByOne(int[] arr, int n) { int temp = arr[0], i; for (i = 0; i < n-1; i++) { arr[i] = arr[i+1]; } arr[n-1] = temp;}void printArray(int arr[], int n) { int i; for (i = 0; i < n; i++) { printf("%d ", arr[i]); }}int main(){ int arr[] = {1,2,3,4,5,6,7}; leftRotate(arr, 2, 7); printArray(arr, 7); return 0;}Java 实现：
class RotateArray { void leftRotate(int arr[], int k, int n) { for (int i = 0; i < k; i++) { leftRotateByOne(arr, n); } } void leftRotateByOne(int arr[], int n) { int temp = arr[0]; for (int i = 0; i < n-1; i++){ arr[i] = arr[i+1]; } arr[n-1] = temp; }}Python 实现：
def leftRotate(arr, k, n): for i in range(k): leftRotateByOne(arr, n) def leftRotateByOne(arr, n): temp = arr[0]; for i in range(n-1): arr[i] = arr[i-1] arr[n-1] = temp算法重要的不是实现，而是思维，但没有实现也万万不能。
复杂度剖析
- 工夫复杂度：$O(kn)$
- 空间复杂度：$\Theta(1)$
办法三（最大公约数法）
此办法是对办法二的扩大，办法二是一步一步地挪动元素，此办法则是依照 n 和 k 的最大公约数挪动元素。
比方，arr[] = {1,2,3,4,5,6,7,8,9,10,11,12} ，k = 3，n = 12 。
计算 gcd(3,12) = 3 ，只须要挪动 3 轮就可能失去数组中的元素向左旋转 k 个地位的后果。
第 1 轮：i = 0 ，temp = arr[i]= arr[0] = 1 ，挪动 arr[j + k] 到 arr[j] ，留神 0 <= j+k < n ；i 示意挪动轮数的计数器，j 示意数组下标，如图 3-1 所示。
<p align='center'>图 3-1 最大公约数法--第 1 轮</p>
第 2 轮：i = 1 ，temp = arr[1] = 2 ，挪动 arr[j + 3] 到 arr[j] , 其中 1 <= j <= 7 。如图 3-2 所示。
<p align='center'>图 3-2 最大公约数法--第 2 轮</p>
第 3 轮：i = 2 , temp = arr[2] = 3 ，挪动 arr[j + 3] 到 arr[j] , 其中 2 <= j <= 8 如图 3-3 所示。
<p align='center'>图 3-3 最大公约数法--第 3 轮</p>
实现代码
C 语言
#include <stdio.h>// 计算 k 和 n 的最大公约数 gcdint gcd(int a, int b){ if(b == 0){ return a; } else{ return gcd(b, a % b); }}void leftRotate(int arr[], int k, int n){ int i,j,s,temp; k = k % n; // 能够缩小不必要的挪动 int g_c_d = gcd(k, n); // 管制外层循环的执行次数 for(i = 0; i < g_c_d; i++){ temp = arr[i]; // 1.将 arr[i] 保留至 temp j = i; // 2. 挪动 arr[j+k] 到 arr[j] while(1){ s = j + k; // 思考将arr[j+k] 的元素挪动到 arr[j] if (s >= n) // 排除 j+k >= n 的状况，j+k < n s = s - n; if (s == i) break; arr[j] = arr[s]; j = s; } arr[j] = temp; // 3.将 temp 保留至 arr[j] }}int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12 }; int i; leftRotate(arr, 3, 12); for(i = 0; i < 12; i++){ printf("%d ", arr[i]); } getchar(); return 0; } while 循环外面解决的就是将 arr[j+k] 挪动到 arr[j] 的过程，比方第 1 轮挪动中，s 的变动如图 3-4 所示，留神当 s = j + k 越界时的解决，与数组下标的边边界值 n 进行比拟，当 s >= n 时，下标越界，则 s = s - n ，继而判断 s == i ，如果相等则退出 while 循环，一轮挪动完结：
<p align='center'>图 3-4 一轮旋转数组下标的变动</p>
被迫练习：尝试本人模仿 n = 12, k = 8 的状况 （练习后点击下方的空白区域可查看参考答案）。
Java 实现代码
class RotateArray { // 将数组 arr 向左旋转 k 个地位 void leftRotate(int arr[], int k, int n) { // 解决 k >= n 的状况，比方 k = 13, n = 12 k = k % n; int i, j, s, temp; // s = j + k; int gcd = gcd(k, n); for (i = 0; i < gcd; i++) { // 第 i 轮挪动元素 temp = arr[i]; j = i; while (true) { s = j + k; if (s >= n) { s = s - n; } if (s == i) { break; } arr[j] = arr[s]; j = s; } arr[j] = temp; } } int gcd(int a, int b) { if(b == 0) { return a; } else{ return gcd(b, a % b); } } public static void main(String[] args) { int arr[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}; RotateArray ra = new RotateArray(); ra.leftRotate(arr, 8, 12); for (int i = 0; i < arr.length; i++) { System.out.print(arr[i] + " "); } }} Python 实现
def leftRotate(arr, k, n): k = k % n g_c_d = gcd(k, n) for i in range(g_c_d): temp = arr[i] j = i while 1: s = j + k if s >= n: s = s - n if s == i: break arr[j] = arr[s] j = s arr[j] = tempdef gcd(a, b): if b == 0: return a else return gcd(b, a % b)arr = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]n = len(arr)leftRotate(arr, 3, n)for i in range(n): print ("%d" % arr[i], end = " ")复杂度剖析
- 工夫复杂度：$O(n)$
- 空间复杂度：$\Theta(1)$
办法四（块交换法）
数组 arr[] = [1,2,3,4,5,6,7] ，其中 k = 2 ，n = 7 。
设数组 arr[0,...,n-1] 蕴含两块 A = arr[0,...,d-1] ，B = arr[d,...,n-1] ，那么将数组 arr 左旋 2 个地位后的后果 arr[] = [3,4,5,6,7,1,2] 就相当于将 A 和 B 进行替换，如图 4-1 所示。
<p align='center'>图 4-1 块交换法</p>
第一步：判断 A 和 B 的大小， A 的长度比 B 小，则将 B 宰割成 Bl 和 Br 两局部，其中 Br 的长度等于 A 的长度。替换 A 和 Br ，即原数组 ABlBr 变成了 BrBlA 。此时 A 曾经放到了正确的地位，而后递归的解决 B 的局部，如图 4-2 所示。
<p align='center'>图 4-2 块交换法(ABlBr --> BrBlA)</p>
第二步：递归解决 B 局部，此时图 4-2 中的 Br 就是新的 A ，Bl 就是新的 B ，判断 A 和 B 的大小，解决与第一步相似，如图 4-3 所示：
<p align='center'>图 4-3 块交换法(递归解决 B 局部)</p>
第三步：递归解决 B 局部，图 4-3 中的 Br 就是新的 A ，Bl 就是新的 B ，判断 A 和 B 的大小， A 的长度比 B 大，将 A 宰割成 Al 和 Ar 两局部，其中 Al 的长度等于 B 的长度。替换 Al 和 B ，则 AlArB 变成了 BArAl ，此时 B 曾经回到正确的地位了；递归解决 A ，如图 4-4 所示。
<p align='center'>图 4-4 块交换法(第 3 步)</p>
第四步：递归解决 A ，图 4-4 中的 Al 就是新的 B ，Ar 就是新的 A ，此时 A 的长度等于 B 的长度，间接替换 A 和 B 即可，如图 4-5 所示。
<p align='center'>图 4-5 块交换法(递归解决 A 局部)</p>
实现代码
递归实现
C 语言递归实现
#include <stdio.h>// 进行块替换，la就相当于块A的第一个元素，lb相当于块B的第一个元素void swap(int arr[], int la, int lb, int d) { int i, temp; for(i = 0; i < d; i++) { temp = arr[la+i]; arr[la+i] = arr[lb+i]; arr[lb+i] = temp; }}void leftRotate(int arr[], int k, int n) { if(k == 0 || k == n) return; // A 和 B 的长度相等，则替换间接替换A,B if(n-k == k) { swap(arr, 0, n-k, k); return; } // A 的长度小于 B, 则将B 宰割成 Bl 和 Br, ABlBr --> BrBlA if(k < n-k) { swap(arr, 0, n-k, k); leftRotate(arr, k, n-k); } else // A 的长度大于 B, 则将 A 宰割为 Al 和 Ar, AlArB --> BArAl { swap(arr, 0, k, n-k); leftRotate(arr+n-k, 2*k-n, k); }}void printArray(int arr[], int size){ int i; for(i = 0; i < size; i++) printf("%d ", arr[i]); printf("\n ");} int main(){ int arr[] = {1, 2, 3, 4, 5, 6, 7}; leftRotate(arr, 2, 7); printArray(arr, 7); getchar(); return 0;}留神： arr+n-k 示意的是一个地址值，示意 Ar 第一个元素的地位。其中数组名 arr 示意数组中第一个元素的首地址。
Java 递归实现代码
import java.util.*;class BockSwap{ // 对递归调用进行包装 public static void leftRotate(int arr[], int k, int n) { leftRotateRec(arr, 0, k, n); } public static void leftRotateRec(int arr[], int i, int k, int n) { // 如果被旋转的个数为 0 或者 n，则间接退出，无需旋转 if(k == 0 || k == n) return; // A == B 的状况，swap(A,B) if(n - k == k) { swap(arr, i, n - k + i, k); return; } // A < B，swap(A,Br), ABlBr --> BrBlA if(k < n - k) { swap(arr, i, n - k + i, k); leftRotateRec(arr, i, k, n - k); } else // A > B , swap(Al, B), AlArB-->BArAl { swap(arr, i, k, n - k); leftRotateRec(arr, n - k + i, 2 * k - n, k); } } // 打印 public static void printArray(int arr[]) { for(int i = 0; i < arr.length; i++) System.out.print(arr[i] + " "); System.out.println(); } // 块替换 public static void swap(int arr[], int la, int lb, int d) { int i, temp; for(i = 0; i < d; i++) { temp = arr[la+i]; arr[la+i] = arr[lb+i]; arr[lb+i] = temp; } } public static void main (String[] args) { int arr[] = {1, 2, 3, 4, 5, 6, 7}; leftRotate(arr, 2, 7); printArray(arr); }}Python 递归代码实现
def leftRotate(arr, k, n): leftRotateRec(arr, 0, k, n); def leftRotateRec(arr, i, k, n): if (k == 0 or k == n): return; if (n - k == k): swap(arr, i, n - k + i, k); return; if (k < n - k): swap(arr, i, n - k + i, k); leftRotateRec(arr, i, k, n - k); else: swap(arr, i, k, n - k); leftRotateRec(arr, n - k + i, 2 * k - n, k); def printArray(arr, size): for i in range(size): print(arr[i], end = " "); print(); def swap(arr, la, lb, d): for i in range(d): temp = arr[la + i]; arr[la + i] = arr[lb + i]; arr[lb + i] = temp; if __name__ == '__main__': arr = [1, 2, 3, 4, 5, 6, 7]; leftRotate(arr, 2, 7); printArray(arr, 7);迭代实现
C 语言迭代实现代码：
void leftRotate(int arr[], int k, int n) { int i, j; if( k == 0 || k == n ) { return; } i = k; j = n - k; while (i != j) { if(i < j) // A < B { swap(arr, k-i, j-i+k, i); j -= i; } else { swap(arr, k-i, k, j); i -= j; } } swap(arr, k-i, k, i);}Java 语言迭代实现代码：
public static void leftRotate(int arr[], int d, int n) { int i, j; if (d == 0 || d == n) return; i = d; j = n - d; while (i != j) { if (i < j) { swap(arr, d - i, d + j - i, i); j -= i; } else { swap(arr, d - i, d, j); i -= j; } } swap(arr, d - i, d, i);}Python 迭代实现代码：
def leftRotate(arr, k, n): if(k == 0 or k == n): return; i = k j = n - k while (i != j): if(i < j): # A < B swap(arr, k - i, k + j - i, i) j -= i else: # A > B swap(arr, k - i, k, j) i -= j swap(arr, k - i, k, i) # A == B复杂度剖析
- 工夫复杂度：$O(n)$
- 空间复杂度：$\Theta(1)$
办法五（反转法）
反转法也可当作逆推法，已知原数组为 arr[] = [1,2,3,4,5,6,7] ，左旋 2 个地位之后的数组为 [3,4,5,6,7,1,2] ，那么有没有什么办法由旋转后的数组失去原数组呢？
首先将 [3,4,5,6,7,1,2] 反转，如图 5-4 所示：
<p align='center'>图 5-1 reverse(arr, 0, n)</p>
而后将 [2,1] 反转过去，将 [7,6,5,4,3] 反转过去，失去如图 5-2 所示的后果：
<p align='center'>图 5-2 reverse(arr, 0, k)，reverse(arr,k,n)</p>
数组左旋 k 个地位的算法如下，图 5-3 所示：
leftRotate(arr[], k, n) reverse(arr[], 0, k); reverse(arr[], k, n); reverse(arr[], 0, n);<p align='center'>图 5-3 反转法(三步走)</p>
实现代码
#include <stdio.h> void printArray(int arr[], int size); void reverseArray(int arr[], int start, int end); // 将数组左旋 k 个地位void leftRotate(int arr[], int k, int n) { if (k == 0 || k == n) return; // 避免旋转参数 k 大于数组长度 k = k % n; reverseArray(arr, 0, k - 1); reverseArray(arr, k, n - 1); reverseArray(arr, 0, n - 1); } // 打印输出void printArray(int arr[], int size) { int i; for (i = 0; i < size; i++) printf("%d ", arr[i]); } // 反转数组void reverseArray(int arr[], int start, int end) { int temp; while (start < end) { temp = arr[start]; arr[start] = arr[end]; arr[end] = temp; start++; end--; } } // 主函数int main() { int arr[] = { 1, 2, 3, 4, 5, 6, 7 }; int n = sizeof(arr) / sizeof(arr[0]); int k = 2; leftRotate(arr, k, n); printArray(arr, n); return 0; }复杂度剖析
- 工夫复杂度：$O(n)$
- 空间复杂度：$\Theta(1)$
算法就是解决问题的办法，而解决问题的形式有很多种，适宜本人的才是最好的。学好算法，缓缓地大家就会发现自己解决问题的形式变了，变得更高效和欠缺啦！
2021 年，牛气冲天！别忘了去 leetcode 刷 189 题呀！
本文来自程序员景禹的公众号：景禹的历史文章