旋轉陣列分為左旋轉和右旋轉兩類，力扣 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<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;}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; }}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 所示。
圖 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 <stdio.h>// 計算 k 和 n 的最大公約數 gcdint 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 一輪旋轉陣列下標的變化
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] + " "); } }} 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] = tempdef 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 題呀！