Rotate Arrays in Java – 用 Java 旋转数组

1. Overview

1.概述

In this tutorial, we’ll learn some algorithms for array rotation in Java.

在本教程中，我们将学习 Java 中 数组旋转的一些算法。

We’ll see how to rotate the array elements k times to the right. We’ll also understand how to modify the array in place, although we might use extra space to compute the rotation.

我们将看到如何将数组元素向右旋转 k 倍。我们还将了解如何就地修改数组，尽管我们可能会使用额外的空间来计算旋转。

2. Introduction to Array Rotation

2.阵列旋转介绍

Before digging into some solutions, let’s discuss how to start thinking about the algorithm.

在探讨一些解决方案之前，我们先来讨论一下如何开始思考算法。

We’ll alias the rotation number with the letter k.

我们将用字母 k 来别名旋转编号。

2.1. Find the Smallest Rotation

2.1.求最小旋转

We’ll transform k to the remainder of k divided by the array length, or k modulo (%) of the array length. This allows us to translate a large rotation number to a relatively small one.

我们将 k 转换为 k 除以数组长度的余数，或 k modulo (%) 数组长度。这样，我们就可以将较大的旋转数转换为相对较小的旋转数。

2.2. Unit Testing

2.2.单元测试

We might want to test k less than, equal to, and greater than the array length. For example, if we rotate 8 times an array of 6 elements, we’ll need only a 2-cycle rotation.

我们可能需要测试 k 小于、等于和大于数组长度。例如，如果我们将一个包含 6 个元素的数组旋转 8 次，我们只需要旋转 2 个周期。

Similarly, we shouldn’t modify the array if k is equal to the array length. Thus, this is something we need to consider as an edge case.

同样，如果 k 等于数组长度，我们就不应该修改数组。因此，这是我们需要考虑的边缘情况。

Finally, we should also check whether the input array isn’t null or k is greater than zero.

最后，我们还应检查输入数组是否为空或 k 是否大于零。

2.3. Array and Rotation Testing Variables

2.3.阵列和旋转测试变量

We’ll set the following variables:

我们将设置以下变量

• arr as the array to test length 6
• rotationLtArrayLength = 1 as a rotation less than the array length
• rotationGtArrayLength = 8 as a rotation greater than the array length
• ltArrayLengthRotation as the solution for rotationLtArrayLength
• gtArrayLengthRotation as the solution for rotationGtArrayLength

Let’s look at their initial values:

让我们来看看它们的初始值：

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. Space and Time Complexity

2.4.时空复杂性

Nonetheless, we must be confident with time and space complexity concepts to understand the algorithm solution.

不过，我们必须对时间和空间复杂性概念有信心，才能理解算法的解决方案。

3. Brute Force

3.蛮力

It’s a common approach to try solving a problem with brute force. This might not be an efficient solution. However, it helps to understand the problem space.

尝试用蛮力解决问题是一种常见的方法。这可能不是一个有效的解决方案。但是，它有助于理解问题空间。

3.1. Algorithm

3.1.算法

We solve by rotating in k steps while shifting the elements by one unit in each step.

我们以 k 步旋转求解，同时每一步将元素移动一个单位。

Let’s have a look at the method:

让我们来看看这种方法：

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. Code Insight

3.2.代码洞察力

We iterate over the array length twice with a nested loop. At first, we get a value we want to rotate at index i:

我们通过嵌套循环对数组长度进行两次遍历。首先，我们在索引 i: 处得到一个要旋转的值。

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

Then, we shift all the elements in the nested for loop by one using a temporary variable.

然后，我们使用临时变量将嵌套 for 循环中的所有元素逐个移动。

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

3.3. Complexity Analysis

3.3.复杂性分析

• Time complexity: O(n×k). All the numbers are shifted by one step O(n) for k times.
• Space complexity: O(1). Constant extra space is used.

3.4. Unit Test

3.4.单元测试

Let’s write a test for the brute force algorithm when k is less than the array length:

让我们为 k 小于数组长度时的暴力算法编写一个测试：

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

Likewise, we test k greater than the array length:

同样，我们测试 k 是否大于数组长度：

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

Finally, let’s test k equal to the array length:

最后，让我们测试 k 是否等于数组长度：

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

4. Rotation With Extra Array

4.带额外阵列的旋转

We use an extra array to place every element at its correct position. Then, we copy back to the original one.

我们使用一个额外的数组将每个元素放在正确的位置上。然后，我们复制回原来的数组。

4.1. Algorithm

4.1.算法

To get the rotated position, we’ll find the (i +k ) position module (%) of the array length:

要获得旋转位置，我们要找到数组长度的 (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);
}

Notably, although not required, we could return the extra array.

值得注意的是，虽然不是必需的，但我们可以返回额外的数组。

4.2. Code Insight

4.2.代码洞察力

We move every element from i to the (i + k) % arr.length position in an extra space array.

我们将 i 中的每个元素移动到额外空格数组中的 (i + k) % arr.length 位置。

Finally, we copy it to the original one using System.arraycopy().

最后，我们使用 System.arraycopy() 将其复制到原始数据中。

4.3. Complexity Analysis

4.3.复杂性分析

• Time complexity: O$(n)$. We have one pass to apply rotation in the new array from which we copy, in another step, over to the original one.
• Space complexity: O(n). We use another array of the same size to store the rotation.

4.4. Unit Test

4.4.单元测试

Let’s test the rotation with this extra array algorithm when k is less than the array length:

让我们测试一下当 k 小于数组长度时，使用这种额外的数组算法进行旋转的情况：

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

Likewise, we test k greater than the array length:

同样，我们测试 k 是否大于数组长度：

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

Finally, let’s test k equal to the array length:

最后，让我们测试 k 是否等于数组长度：

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

5. Cyclic Replacements

5.周期性更换

We could replace an element at its required position every time. However, we’d lose the original value. Therefore, we’ll store it in a temporary variable. Then, we can place the rotated element for n times, where n is the array length.

我们可以每次都在所需位置替换元素。但是，我们会丢失原来的值。因此，我们将其存储在一个临时变量中。然后，我们可以将旋转过的元素放置 n 次，其中 n 是数组长度。

5.1. Algorithm

5.1.算法

We can see the logic of the cyclic replacement in the diagram for k = 2:

我们可以从 k = 2 的图表中看出循环替换的逻辑：</em

So, we start from the index 0 and do 2-step cycles.

因此，我们从索引 0 开始，进行两步循环。

However, there is an issue with this approach. As we might notice, we can return to the initial array position. In that case, we’ll start again as a regular for-loop cycle.

然而，这种方法存在一个问题。我们可能会注意到，我们可以返回到数组的初始位置。在这种情况下，我们将以普通 for 循环的方式重新开始。

Finally, we’ll keep track of the elements we replaced using a count variable. Our cycle will complete when the count is equal to the array length.

最后，我们将使用 count 变量来跟踪我们替换的元素。当 count 等于数组长度时，我们的循环就完成了。

Let’s look at the code:

让我们看看代码：

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. Code Insight

5.2.代码洞察力

There are two parts we need to focus on for this algorithm.

对于这种算法，我们需要关注两个部分。

The first one is the outer loop. We iterate for every n/k fraction of elements we replace in a k-step cycle:

第一个是外循环。在 k 步循环中，我们每替换 n/k 部分元素，就进行一次迭代：

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

Therefore, we use a do-while-loop to shift a value by k steps (while saving the replaced value) until we reach the number from which we originally started and go back to the outer loop:

因此，我们使用do-while-loop将一个值移动k步（同时保存被替换的值），直到达到最初开始的数字，然后返回外循环：

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

5.3. Complexity Analysis

5.3.复杂性分析

• Time complexity: O(n)
• Space complexity: O(1). Constant extra space is used.

5.4. Unit Test

5.4.单元测试

Let’s test the cyclic replacement array algorithm when k is less than the array length:

让我们测试一下当 k 小于数组长度时的循环替换数组算法：

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

Likewise, we test k greater than the array length:

同样，我们测试 k 是否大于数组长度：

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

Finally, let’s test k equal to the array length:

最后，让我们测试 k 是否等于数组长度：

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

6. Reverse

6.反向

This is a simple yet non-trivial algorithm. When we rotate, we might notice that k elements from the back end of the array come to the front, and the rest of the elements from the front shift backward.

这是一种简单但并不复杂的算法。当我们旋转时，我们可能会注意到，k元素从数组的后端来到前端，而其余元素则从前端向后移动。

6.1. Algorithm

6.1.算法

We solve with three steps in which we reverse:

我们通过三个步骤来逆向解决：

• All the elements of the array
• The first k elements
• The remaining (n-k) elements

Let’s have a look at the code:

让我们来看看代码：

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. Code Insight

6.2.代码洞察力

We use a helper method similar to brute force’s nested loop. However, we do it in three different steps this time:

我们使用的辅助方法与暴力嵌套循环类似。不过，这次我们分三个不同的步骤进行：

We reverse the whole array:

我们推翻了整个阵列：

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

Then, we reverse the first k elements.

然后，我们将前 k 个元素倒转。

reverse(arr, 0, k - 1);

Finally, we reverse the remaining elements:

最后，我们推翻了其余要素：

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

Although this seems to introduce redundancy, it’ll allow us to complete the task in linear time.

虽然这似乎会带来冗余，但却能让我们在线性时间内完成任务。

6.3. Complexity Analysis

6.3.复杂性分析

• Time complexity: O(n). n elements are reversed a total of three times.
• Space complexity: O(1). Constant extra space is used.

6.4. Unit Test

6.4.单元测试

Let’s test the reverse algorithm when k is less than the array length:

让我们测试一下 k 小于数组长度时的反向算法：

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

Likewise, we test k greater than the array length:

同样，我们测试 k 是否大于数组长度：

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

Finally, let’s test k equal to the array length:

最后，让我们测试 k 是否等于数组长度：

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

7. Conclusion

7.结论

In this article, we saw how to rotate an array by k rotations. We started with brute force and then moved to more complex algorithms like reverse or cyclic replacements with no extra space. We also talked about the time and space complexity. Finally, we discussed unit testing and some edge cases.

在本文中，我们了解了如何通过 k 次旋转来旋转数组。我们从蛮力开始，然后转向更复杂的算法，如反向或无额外空间的循环替换。我们还讨论了时间和空间复杂性。最后，我们讨论了单元测试和一些边缘案例。

As always, the code presented in this article is available over on GitHub.

与往常一样，本文中介绍的代码可在 GitHub 上获取。