乐趣区

关于微信公众平台:图解什么是旋转数组Rotate-Array

旋转数组

一文横扫数组基础知识

旋转数组分为左旋转和右旋转两类,力扣 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 = 0temp = arr[i]= arr[0] = 1,挪动 arr[j + k]arr[j],留神 0 <= j+k < ni 示意挪动轮数的计数器,j 示意数组下标,如图 3-1 所示。

<p align=’center’> 图 3-1 最大公约数法 – 第 1 轮 </p>

第 2 轮:i = 1temp = 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 = 2n = 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] 就相当于将 AB 进行替换,如图 4-1 所示。

<p align=’center’> 图 4-1 块交换法 </p>

第一步:判断 AB 的大小,A 的长度比 B 小,则将 B 宰割成 BlBr 两局部,其中 Br 的长度等于 A 的长度。替换 ABr,即原数组 ABlBr 变成了 BrBlA。此时 A 曾经放到了正确的地位,而后递归的解决 B 的局部,如图 4-2 所示。

<p align=’center’> 图 4-2 块交换法 (ABlBr –> BrBlA)</p>

第二步:递归解决 B 局部,此时图 4-2 中的 Br 就是新的 ABl 就是新的 B,判断 AB 的大小,解决与第一步相似,如图 4-3 所示:

<p align=’center’> 图 4-3 块交换法 (递归解决 B 局部)</p>

第三步:递归解决 B 局部,图 4-3 中的 Br 就是新的 ABl 就是新的 B,判断 AB 的大小,A 的长度比 B 大,将 A 宰割成 AlAr 两局部,其中 Al 的长度等于 B 的长度。替换 AlB,则 AlArB 变成了 BArAl,此时 B 曾经回到正确的地位了;递归解决 A,如图 4-4 所示。

<p align=’center’> 图 4-4 块交换法 (第 3 步)</p>

第四步:递归解决 A,图 4-4 中的 Al 就是新的 BAr 就是新的 A,此时 A 的长度等于 B 的长度,间接替换 AB 即可,如图 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 题呀!

本文来自程序员景禹的公众号:景禹的历史文章

退出移动版