旋转数组
一文横扫数组基础知识
旋转数组分为左旋转和右旋转两类，力扣 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 的最大公约数 gcd
int 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] = temp
def 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 题呀！
本文来自程序员景禹的公众号：景禹的历史文章