| 图解：什么是旋转数组（Rotate Array)？ | 您所在的位置：网站首页 › 左旋原理是什么 › 图解：什么是旋转数组（Rotate Array)？ |
图解：什么是旋转数组（Rotate Array)？
|
旋转数组
一文横扫数组基础知识 旋转数组分为左旋转和右旋转两类，力扣 189 题为右旋转的情况，今日分享的为左旋转。 给定一个数组，将数组中的元素向左旋转 k 个位置，其中 k 是非负数。
图 0-1 数组 arr 左旋转 k=2 个位置 原数组为 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 所示。
图 1-1 临时数组法 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 所示。
图 2-1 按部就班左旋法 实现代码 C 语言实现 // c 语言实现，学习算法重要的是思想，实现要求的是基础语法 #include 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算法重要的不是实现，而是思想，但没有实现也万万不能。 复 |
【本文地址】