旋轉數組(Rotate Array)

來源 |景禹（微信公眾號ID：LifeAtaraxia）

旋轉數組

旋轉數組分為左旋轉和右旋轉兩類，力扣 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];
    }
} 
複雜度分析方法二（按部就班移動法）

按部就班就是按照左旋轉的定義一步一步地移動。

對於第一次旋轉，將 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

算法重要的不是實現，而是思想，但沒有實現也萬萬不能。

複雜度分析方法三（最大公約數法）

此方法是對方法二的擴展，方法二是一步一步地移動元素，此方法則是按照 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 輪

實現代碼C 語言#include 
// 計算 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 
// 進行塊交換，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  
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 題呀！

  推薦閱讀：

用三國殺講分布式算法，舒適了吧？

漫畫：如何螺旋遍歷二維數組？（修訂版）

數組 vs 鍊表，到底哪個性能更強？