在 Java 中旋轉數組

1. 概述

在本教程中，我們將學習一些 Java 中數組旋轉的演算法。

我們將看到如何將陣列元素向右旋轉k次。我們還將了解如何就地修改數組，儘管我們可能會使用額外的空間來計算旋轉。

2. 數組旋轉簡介

在深入研究一些解決方案之前，我們先討論如何開始思考演算法。

我們將用字母k為旋轉數起別名。

2.1.找到最小的旋轉

我們將把k轉換為k除以數組長度的餘數，或k對數組長度取模 ( % ) 。這使我們能夠將較大的旋轉數轉換為相對較小的旋轉數。

2.2.單元測試

我們可能想要測試k小於、等於和大於陣列 length 。例如，如果我們將 6 個元素的陣列旋轉 8 次，則只需要 2 個週期的旋轉。

同樣，如果k等於數組長度，我們就不應該修改數組。因此，這是我們需要考慮的邊緣情況。

最後，我們也應該檢查輸入陣列是否不為空或k是否大於零。

2.3.數組和旋轉測試變量

我們將設定以下變數：

• arr作為要測試長度6陣列
• rotationLtArrayLength = 1作為小於數組長度的旋轉
• rotationGtArrayLength = 8作為大於數組長度的旋轉
• ltArrayLengthRotation作為rotationLtArrayLength的解決方案
• gtArrayLengthRotation作為rotationGtArrayLength解決方案GtArrayLength

讓我們看看它們的初始值：

int[] arr = { 1, 2, 3, 4, 5, 6 };
 int rotationLtArrayLength = 1;
 int rotationGtArrayLength = arr.length + 2;
 int[] ltArrayLengthRotation = { 6, 1, 2, 3, 4, 5 };
 int[] gtArrayLengthRotation = { 5, 6, 1, 2, 3, 4 };

2.4.空間和時間複雜度

儘管如此，我們必須對時間和空間複雜度概念充滿信心，才能理解演算法解決方案。

3. 暴力破解

嘗試用蠻力解決問題是常見的方法。這可能不是一個有效的解決方案。然而，它有助於理解問題空間。

3.1.演算法

我們透過旋轉k步來求解，同時每一步將元素移動一個單位。

我們來看看方法：

void bruteForce(int[] arr, int k) {
 // check invalid input
 k %= arr.length;
 int temp;
 int previous;
 for (int i = 0; i < k; i++) {
 previous = arr[arr.length - 1];
 for (int j = 0; j < arr.length; j++) {
 temp = arr[j];
 arr[j] = previous;
 previous = temp;
 }
 }
 }

3.2.程式碼洞察

我們使用巢狀循環對數組長度進行兩次迭代。首先，我們得到一個要在索引i:

for (int i = 0; i < k; i++) {
 previous = arr[arr.length - 1];
 // nested loop
 }

然後，我們使用臨時變數將嵌套for迴圈中的所有元素移一。

for (int j = 0; j < arr.length; j++) {
 temp = arr[j];
 arr[j] = previous;
 previous = temp;
 }

3.3.複雜性分析

• 時間複雜度： O(n×k) 。所有數字都移動一步O(n) k次。
• 空間複雜度： O(1) 。使用恆定的額外空間。

3.4.單元測試

讓我們為k小於數組長度時的暴力演算法寫一個測試：

@Test
 void givenInputArray_whenUseBruteForceRotationLtArrayLength_thenRotateArrayOk() {
 bruteForce(arr, rotationLtArrayLength);
 assertArrayEquals(ltArrayLengthRotation, arr);
 }

同樣，我們測試k是否大於數組長度：

@Test
 void givenInputArray_whenUseBruteForceRotationGtArrayLength_thenRotateArrayOk() {
 bruteForce(arr, rotationGtArrayLength);
 assertArrayEquals(gtArrayLengthRotation, arr);
 }

最後，讓我們測試一下k是否等於陣列長度：

@Test
 void givenInputArray_whenUseBruteForceRotationEqArrayLength_thenDoNothing() {
 int[] expected = arr.clone();
 bruteForce(arr, arr.length);
 assertArrayEquals(expected, arr);
 }

4. 使用額外陣列進行旋轉

我們使用一個額外的陣列將每個元素放置在正確的位置。然後，我們複製回原來的。

4.1.演算法

為了獲得旋轉位置，我們將找到數組長度的 ( i +k ) 位置模組 ( % )：

void withExtraArray(int[] arr, int k) {
 // check invalid input

 int[] extraArray = new int[arr.length];
 for (int i = 0; i < arr.length; i++) {
 extraArray[(i + k) % arr.length] = arr[i];
 }
 System.arraycopy(extraArray, 0, arr, 0, arr.length);
 }

值得注意的是，雖然不是必需的，但我們可以傳回額外的陣列。

4.2.程式碼洞察

我們將每個元素從i移動到額外空間數組中的(i + k) % arr.length位置。

最後，我們使用System.arraycopy()將其複製到原始陣列。

4.3.複雜性分析

• 時間複雜度：O ( n ) 。我們有一次在新數組中應用旋轉，我們在另一個步驟中將其複製到原始數組。
• 空間複雜度： **O(n)** 。我們使用另一個相同大小的陣列來儲存旋轉。

4.4.單元測試

當k小於陣列長度時，讓我們用這個額外的陣列演算法來測試旋轉：

@Test
 void givenInputArray_whenUseExtraArrayRotationLtArrayLength_thenRotateArrayOk() {
 withExtraArray(arr, rotationLtArrayLength);
 assertArrayEquals(ltArrayLengthRotation, arr);
 }

同樣，我們測試k是否大於數組長度：

@Test
 void givenInputArray_whenUseExtraArrayRotationGtArrayLength_thenRotateArrayOk() {
 withExtraArray(arr, rotationGtArrayLength);
 assertArrayEquals(gtArrayLengthRotation, arr);
 }

最後，讓我們測試一下k是否等於陣列長度：

@Test
 void givenInputArray_whenUseExtraArrayWithRotationEqArrayLength_thenDoNothing() {
 int[] expected = arr.clone();
 withExtraArray(arr, arr.length);
 assertArrayEquals(expected, arr);
 }

5. 循環更換

我們每次都可以在所需的位置替換一個元素。然而，我們會失去原來的價值。因此，我們將其儲存在一個臨時變數中。然後，我們可以將旋轉的元素放置n次，其中n是數組長度。

5.1.演算法

我們可以在圖中看到k = 2:

因此，我們從索引 0 開始，進行 2 步驟循環。

然而，這種方法有一個問題。正如我們可能注意到的，我們可以返回初始數組位置。在這種情況下，我們將重新開始常規的 for 迴圈。

最後，我們將使用count變數來追蹤替換的元素。當count等於數組長度時，我們的循環將完成。

我們來看一下程式碼：

void cyclicReplacement(int[] arr, int k) {
 // check invalid input

 k = k % arr.length;
 int count = 0;
 for (int start = 0; count < arr.length; start++) {
 int current = start;
 int prev = arr[start];
 do {
 int next = (current + k) % arr.length;
 int temp = arr[next];
 arr[next] = prev;
 prev = temp;
 current = next;
 count++;
 } while (start != current);
 }
 }

5.2.程式碼洞察

對於這個演算法，我們需要關注兩個部分。

第一個是外循環。我們對在 k 步循環中替換的每個n/k元素進行迭代：

for (int start = 0; count < arr.length; start++) {
 int current = start;
 int prev = arr[start];
 do {
 // do loop
 } while (start != current);
 }

因此，我們使用do-while-loop將值移動k步（同時保存替換的值），直到達到最初開始的數字並返回到外循環：

int next = (current + k) % arr.length;
 int temp = arr[next];
 arr[next] = prev;
 prev = temp;
 current = next;
 count++;

5.3.複雜性分析

• 時間複雜度： O(n)
• 空間複雜度： **O(1)** 。使用恆定的額外空間。

5.4.單元測試

讓我們來測試一下當k小於數組長度時的循環替換數組演算法：

@Test
 void givenInputArray_whenUseCyclicReplacementRotationLtArrayLength_thenRotateArrayOk() {
 cyclicReplacement(arr, rotationLtArrayLength);
 assertArrayEquals(ltArrayLengthRotation, arr);
 }

同樣，我們測試k是否大於數組長度：

@Test
 void givenInputArray_whenUseCyclicReplacementRotationGtArrayLength_thenRotateArrayOk() {
 cyclicReplacement(arr, rotationGtArrayLength);
 assertArrayEquals(gtArrayLengthRotation, arr);
 }

最後，讓我們測試一下k是否等於陣列長度：

@Test
 void givenInputArray_whenUseCyclicReplacementRotationEqArrayLength_thenDoNothing() {
 int[] expected = arr.clone();
 cyclicReplacement(arr, arr.length);
 assertArrayEquals(expected, arr);
 }

6. 反轉

這是一個簡單但不平凡的演算法。當我們旋轉時，我們可能會注意到數組後端的k元素來到了前面，而前面的其餘元素則向後移動。

6.1.演算法

我們透過三個步驟進行逆向求解：

• 數組的所有元素
• 前k個元素
• 剩餘（ nk)個元素

我們來看一下程式碼：

void reverse(int[] arr, int k) {
 // check invalid input

 k %= arr.length;
 reverse(arr, 0, arr.length - 1);
 reverse(arr, 0, k - 1);
 reverse(arr, k, arr.length - 1);
 }

 void reverse(int[] nums, int start, int end) {
 while (start < end) {
 int temp = nums[start];
 nums[start] = nums[end];
 nums[end] = temp;
 start++;
 end--;
 }
 }

6.2.程式碼洞察

我們使用類似於暴力破解的嵌套循環的輔助方法。不過，這次我們分三個不同的步驟進行：

我們反轉整個數組：

reverse(arr, 0, arr.length - 1);

然後，我們反轉前k個元素。

reverse(arr, 0, k - 1);

最後，我們反轉剩餘的元素：

reverse(arr, k, arr.length - 1);

儘管這似乎引入了冗餘，但它允許我們在線性時間內完成任務。

6.3.複雜性分析

• 時間複雜度： **O(n).** n元素總共翻轉 3 次。
• 空間複雜度： **O(1)** 。使用恆定的額外空間。

6.4.單元測試

讓我們測試一下當k小於數組長度時的逆向演算法：

@Test
 void givenInputArray_whenUseReverseRotationLtArrayLength_thenRotateArrayOk() {
 reverse(arr, rotationLtArrayLength);
 assertArrayEquals(ltArrayLengthRotation, arr);
 }

同樣，我們測試k是否大於數組長度：

@Test
 void givenInputArray_whenUseReverseRotationGtArrayLength_thenRotateArrayOk() {
 reverse(arr, rotationGtArrayLength);
 assertArrayEquals(gtArrayLengthRotation, arr);
 }

最後，讓我們測試一下k是否等於陣列長度：

@Test
 void givenInputArray_whenUseReverseRotationEqArrayLength_thenDoNothing() {
 int[] expected = arr.clone();
 reverse(arr, arr.length);
 assertArrayEquals(expected, arr);
 }

七、結論

在本文中，我們了解如何將陣列旋轉k次。我們從蠻力開始，然後轉向更複雜的演算法，例如沒有額外空間的反向或循環替換。我們也討論了時間和空間複雜度。最後，我們討論了單元測試和一些邊緣情況。

與往常一樣，本文中提供的程式碼可以在 GitHub 上取得。