快速找到數組的多個左旋轉| 系列 1 · GeeksForGeeks 中文系列教程

# 快速找到數組的多個左旋轉| 系列 1 > 原文： [https://www.geeksforgeeks.org/quickly-find-multiple-left-rotations-of-an-array/](https://www.geeksforgeeks.org/quickly-find-multiple-left-rotations-of-an-array/) 給定大小為 n 的數組和多個值，我們需要圍繞該值左旋轉數組。如何快速找到多個左旋？ **示例**： ``` Input : arr[] = {1, 3, 5, 7, 9} k1 = 1 k2 = 3 k3 = 4 k4 = 6 Output : 3 5 7 9 1 7 9 1 3 5 9 1 3 5 7 3 5 7 9 1 Input : arr[] = {1, 3, 5, 7, 9} k1 = 14 Output : 9 1 3 5 7 ``` **簡單方法**：我們已經在下面的文章中討論了不同的方法。 1. [數組的左旋轉（簡單和雜耍算法）](https://www.geeksforgeeks.org/array-rotation/)。 2. [數組旋轉的塊交換算法](https://www.geeksforgeeks.org/block-swap-algorithm-for-array-rotation/) 3. [數組旋轉的逆向算法](https://www.geeksforgeeks.org/program-for-array-rotation-continued-reversal-algorithm/) 上述方法中的最佳方法需要`O(n)`時間和`O(1)`額外空間。 **高效方法**：當需要單次旋轉時，上述方法效果很好。這些方法還修改了原始數組。為了處理數組旋轉的多個查詢，我們使用大小為 2n 的臨時數組并快速處理旋轉。步驟 1：將整個數組復制到`temp[0..2n-1]`數組中兩次。步驟 2：在`temp[]`中旋轉 k 次后，數組的起始位置將為`k % n`。我們執行 k 步驟 3：從`k % n`到`k % n + n`打印`temp []`數組。 ## C++ ```cpp // CPP implementation of left rotation of // an array K number of times #include<bits/stdc++.h> using namespace std; // Fills temp[] with two copies of arr[] void preprocess(int arr[], int n, int temp[]) { ????// Store arr[] elements at i and i + n ????for (int i = 0; i<n; i++) ?????????temp[i] = temp[i + n] = arr[i]; } // Function to left rotate an array k times void leftRotate(int arr[], int n, int k, int temp[]) { ????// Starting position of array after k ????// rotations in temp[] will be k % n ????int start = k % n; ????// Print array after k rotations ????for (int i = start; i < start + n; i++) ?????????cout << temp[i] << " "; ????cout << endl; } // Driver program int main() { ????int arr[] = {1, 3, 5, 7, 9}; ????int n = sizeof(arr) / sizeof(arr[0]); ????int temp[2*n]; ????preprocess(arr, n, temp); ????int k = 2; ????leftRotate(arr, n, k, temp); ????k = 3; ????leftRotate(arr, n, k, temp); ????k = 4; ????leftRotate(arr, n, k, temp); ????return 0; } ``` ## Java ```java // Java implementation of left rotation of // an array K number of times class LeftRotate { ????// Fills temp[] with two copies of arr[] ????static void preprocess(int arr[], int n, ???????????????????????????????????int temp[]) ????{ ????????// Store arr[] elements at i and i + n ????????for (int i = 0; i<n; i++) ?????????????temp[i] = temp[i + n] = arr[i]; ????} ????// Function to left rotate an array k time ????static void leftRotate(int arr[], int n, int k,? ????????????????????????????????????int temp[]) ????{ ????????// Starting position of array after k ????????// rotations in temp[] will be k % n ????????int start = k % n; ????????// Print array after k rotations ????????for (int i = start; i < start + n; i++) ????????????System.out.print(temp[i] + " "); ????????System.out.print("\n"); ????} ????// Driver program ????public static void main (String[] args) ????{ ????????int arr[] = {1, 3, 5, 7, 9}; ????????int n = arr.length; ????????int temp[] = new int[2*n]; ????????preprocess(arr, n, temp); ????????int k = 2; ????????leftRotate(arr, n, k, temp); ????????k = 3; ????????leftRotate(arr, n, k, temp); ????????k = 4; ????????leftRotate(arr, n, k, temp); ????} } /*This code is contributed by Prakriti Gupta*/ ``` ## Python3 ```py # Python3 implementation of left rotation # of an array K number of times # Fills temp with two copies of arr def preprocess(arr, n): ????temp = [None] * (2 * n) ????# Store arr elements at i and i + n ????for i in range(n): ????????temp[i] = temp[i + n] = arr[i] ????return temp # Function to left rotate an array k times def leftRotate(arr, n, k, temp): ????# Starting position of array after k ????# rotations in temp will be k % n ????start = k % n ????# Print array after k rotations ????for i in range(start, start + n): ????????print(temp[i], end = " ") ????print("") # Driver program arr = [1, 3, 5, 7, 9] n = len(arr) temp = preprocess(arr, n) k = 2 leftRotate(arr, n, k, temp) k = 3 leftRotate(arr, n, k, temp) k = 4 leftRotate(arr, n, k, temp) # This code is contributed by Sanghamitra Mishra? ``` ## C# ```cs // Java implementation of left rotation of // an array K number of times using System; class LeftRotate { ????// Fills temp[] with two copies of arr[] ????static void preprocess(int []arr, int n, ????????????????????????????????int[] temp) ????{ ????????// Store arr[] elements at i and i + n ????????for (int i = 0; i<n; i++) ????????????temp[i] = temp[i + n] = arr[i]; ????} ????// Function to left rotate an array k time ????static void leftRotate(int []arr, int n, int k,? ????????????????????????????????????int []temp) ????{ ????????// Starting position of array after k ????????// rotations in temp[] will be k % n ????????int start = k % n; ????????// Print array after k rotations ????????for (int i = start; i < start + n; i++) ????????Console.Write(temp[i] + " "); ????????Console.WriteLine(); ????} ????// Driver program ????public static void Main () ????{ ????????int []arr = {1, 3, 5, 7, 9}; ????????int n = arr.Length; ????????int []temp = new int[2*n]; ????????preprocess(arr, n, temp); ????????int k = 2; ????????leftRotate(arr, n, k, temp); ????????k = 3; ????????leftRotate(arr, n, k, temp); ????????k = 4; ????????leftRotate(arr, n, k, temp); ????} } //This code is contributed by vt_m. ``` ## PHP ```php <?php? // PHP implementation of? // left rotation of an? // array K number of times // Fills $temp with // two copies of $arr function preprocess(&$arr, $n,? ????????????????????&$temp) { ????// Store $arr elements ????// at i and i + n ????for ($i = 0; $i < $n; $i++) ????????$temp[$i] = $temp[$i + $n] = $arr[$i]; } // Function to left rotate // an array k times function leftRotate(&$arr, $n, ?????????????????????$k, &$temp) { ????// Starting position of? ????// array after k rotations ????// in temp[] will be k % n ????$start = $k % $n; ????// Print array after ????// k rotations ????for ($i = $start;? ?????????$i < $start + $n; $i++) ????????echo $temp[$i] . " "; ????echo "\n"; } // Driver Code $arr = array(1, 3, 5, 7, 9); $n = sizeof($arr); $temp[2 * $n] = array(); preprocess($arr, $n, $temp); $k = 2; leftRotate($arr, $n, $k, $temp); $k = 3; leftRotate($arr, $n, $k, $temp); $k = 4; leftRotate($arr, $n, $k, $temp); // This code is contributed // by ChitraNayal ?> ``` **輸出**： ``` 5 7 9 1 3 7 9 1 3 5 9 1 3 5 7 ``` 注意，查找旋轉起始地址的任務需要**`O(1)`時間**。它正在打印需要`O(n)`時間的元素。 **優化空間的方法**：上述方法需要額外的空間。下面給出的是空間優化的解決方案。感謝 **frenzy77** 提出了這種方法。 ## C++ ``` // CPP implementation of left rotation of // an array K number of times #include<bits/stdc++.h> using namespace std; // Function to left rotate an array k times void leftRotate(int arr[], int n, int k) { ????// Print array after k rotations ????for (int i = k; i < k + n; i++) ????????cout << arr[i%n] << " "; } // Driver program int main() { ????int arr[] = {1, 3, 5, 7, 9}; ????int n = sizeof(arr) / sizeof(arr[0]); ????int k = 2; ????leftRotate(arr, n, k); ????cout << endl; ????k = 3; ????leftRotate(arr, n, k); ????cout << endl; ????k = 4; ????leftRotate(arr, n, k); ????cout << endl; ????return 0; } ``` ## Java ```java // Java implementation of? // left rotation of an? // array K number of times import java.io.*; class GFG { // Function to left rotate // an array k times static void leftRotate(int arr[],? ???????????????????????int n, int k) { ????// Print array after ????// k rotations ????for (int i = k; i < k + n; i++) ????????System.out.print(arr[i % n] + " "); } // Driver Code public static void main (String[] args) { ????int arr[] = {1, 3, 5, 7, 9}; ????int n = arr.length; ????int k = 2; ????leftRotate(arr, n, k); ????System.out.println(); ????k = 3; ????leftRotate(arr, n, k); ????System.out.println(); ????k = 4; ????leftRotate(arr, n, k); ????System.out.println();? } } // This code is contributed by ajit ``` ## Python 3 ``` # Python3 implementation of? # left rotation of an array? # K number of times? # Function to left rotate # an array k times def leftRotate(arr, n, k): ????# Print array? ????# after k rotations ????for i in range(k, k + n): ????????print(str(arr[i % n]),? ???????????????????end = " ") # Driver Code arr = [1, 3, 5, 7, 9] n = len(arr) k = 2; leftRotate(arr, n, k) print() k = 3; leftRotate(arr, n, k) print() k = 4 leftRotate(arr, n, k) print() # This code is contributed? # by ChitraNayal ``` ## C# ``` // C# implementation of? // left rotation of an? // array K number of times using System; class GFG { // Function to left rotate // an array k times static void leftRotate(int []arr,? ???????????????????????int n, int k) { ????// Print array after ????// k rotations ????for (int i = k; i < k + n; i++) ????????Console.Write(arr[i % n] + " "); } // Driver Code static public void Main () { int []arr = {1, 3, 5, 7, 9}; int n = arr.Length; int k = 2; leftRotate(arr, n, k); Console.WriteLine(); k = 3; leftRotate(arr, n, k); Console.WriteLine(); k = 4; leftRotate(arr, n, k); Console.WriteLine();? } } // This code is contributed? // by akt_mit ``` ## PHP ```php <?php // PHP implementation of left rotation of // an array K number of times // Function to left rotate an array k times function leftRotate($arr, $n, $k) { ????// Print array after k rotations ????for ($i = $k; $i < $k + $n; $i++) ????????echo $arr[$i % $n] ," "; } // Driver program $arr = array (1, 3, 5, 7, 9); $n = sizeof($arr); $k = 2; leftRotate($arr, $n, $k); echo "\n"; $k = 3; leftRotate($arr, $n, $k); echo "\n"; $k = 4; leftRotate($arr, $n, $k); echo "\n"; // This code is contributed by aj_36 ?> ``` **輸出**： ``` 5 7 9 1 3 7 9 1 3 5 9 1 3 5 7 ``` 本文由 [**核**](https://www.facebook.com/nuclode) 和 [**Rohit Thapliyal**](https://www.linkedin.com/in/rohit-thapliyal-515b5913a/) 貢獻。如果您喜歡 GeeksforGeeks 并希望做出貢獻，則還可以使用 [tribution.geeksforgeeks.org](http://www.contribute.geeksforgeeks.org) 撰寫文章，或將您的文章郵寄至 tribution@geeksforgeeks.org。查看您的文章出現在 GeeksforGeeks 主頁上，并幫助其他 Geeks。