旋转数组（Rotate Array)
source link: https://www.cxyxiaowu.com/15778.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
旋转数组分为左旋转和右旋转两类，力扣 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];
}
}
复杂度分析
- 时间复杂度： ，n 表示数组的长度。
- 空间复杂度： ，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<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
算法重要的不是实现，而是思想，但没有实现也万万不能。
复杂度分析
- 时间复杂度：
- 空间复杂度：
方法三（最大公约数法）
此方法是对方法二的扩展，方法二是一步一步地移动元素，此方法则是按照 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 所示。
图 3-1 最大公约数法–第 1 轮
第 2 轮：i = 1 ，temp = arr[1] = 2 ，移动 arr[j + 3] 到 arr[j] , 其中 1 <= j <= 7 。如图 3-2 所示。
图 3-2 最大公约数法–第 2 轮
第 3 轮：i = 2 , temp = arr[2] = 3 ，移动 arr[j + 3] 到 arr[j] , 其中 2 <= j <= 8 如图 3-3 所示。
图 3-3 最大公约数法–第 3 轮
#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 循环，一轮移动结束：
图 3-4 一轮旋转数组下标的变化
自愿练习：尝试自己模拟 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 = " ")
复杂度分析
- 时间复杂度：
- 空间复杂度：
方法四（块交换法）
数组 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 所示。
图 4-1 块交换法
第一步：判断 A 和 B 的大小， A 的长度比 B 小，则将 B 分割成 Bl 和 Br 两部分，其中 Br 的长度等于 A 的长度。交换 A 和 Br ，即原数组 ABlBr 变成了 BrBlA 。此时 A 已经放到了正确的位置，然后递归的处理 B 的部分，如图 4-2 所示。
图 4-2 块交换法(ABlBr –> BrBlA)
第二步：递归处理 B 部分，此时图 4-2 中的 Br 就是新的 A ，Bl 就是新的 B ，判断 A 和 B 的大小，处理与第一步类似，如图 4-3 所示：
图 4-3 块交换法(递归处理 B 部分)
第三步：递归处理 B 部分，图 4-3 中的 Br 就是新的 A ，Bl 就是新的 B ，判断 A 和 B 的大小， A 的长度比 B 大，将 A 分割成 Al 和 Ar 两部分，其中 Al 的长度等于 B 的长度。交换 Al 和 B ，则 AlArB 变成了 BArAl ，此时 B 已经回到正确的位置了；递归处理 A ，如图 4-4 所示。
图 4-4 块交换法(第 3 步)
第四步：递归处理 A ，图 4-4 中的 Al 就是新的 B ，Ar 就是新的 A ，此时 A 的长度等于 B 的长度，直接交换 A 和 B 即可，如图 4-5 所示。
图 4-5 块交换法(递归处理 A 部分)
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
复杂度分析
- 时间复杂度：
- 空间复杂度：
方法五（反转法）
反转法也可当作逆推法，已知原数组为 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 所示：
图 5-1 reverse(arr, 0, n)
然后将 [2,1] 反转过来，将 [7,6,5,4,3] 反转过来，得到如图 5-2 所示的结果：
图 5-2 reverse(arr, 0, k)，reverse(arr,k,n)
数组左旋 k 个位置的算法如下，图 5-3 所示：
leftRotate(arr[], k, n)
reverse(arr[], 0, k);
reverse(arr[], k, n);
reverse(arr[], 0, n);
图 5-3 反转法(三步走)
#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;
}
复杂度分析
- 时间复杂度：
- 空间复杂度：
算法就是解决问题的方法，而解决问题的方式有很多种，适合自己的才是最好的。学好算法，慢慢地大家就会发现自己处理问题的方式变了，变得更高效和完善啦！
2021 年，牛气冲天！别忘了去 leetcode 刷 189 题呀！
作者：景禹，一个追求极致的共享主义者，想带你一起拥有更美好的生活，化作你的一把伞。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK