Java数组旋转算法详解

最后修改:2024年1月8日

by Luca Cambi

1. 概述

本教程将介绍几种在Java中实现数组旋转的算法。我们将学习如何将数组元素向右旋转k次，并探讨如何在可能使用额外空间的情况下原地修改数组。

2. 数组旋转基础

在深入算法之前，我们先讨论如何构建旋转算法的思路。这里用字母k表示旋转次数。

2.1. 计算最小旋转次数

我们需要将k转换为k除以数组长度的余数，即k对数组长度取模（%）。这样可以将大旋转次数转换为等效的小旋转次数。

2.2. 单元测试要点

我们需要测试k小于、等于和大于数组长度的情况。例如，当旋转一个长度为6的数组8次时，实际只需要旋转2次。

同样，当k等于数组长度时，数组应保持不变。这是一个需要考虑的边界情况。

最后，我们还需要检查输入数组是否为null，以及k是否大于0。

2.3. 测试变量定义

我们定义以下测试变量：

  • arr：长度为6的测试数组
  • rotationLtArrayLength = 1：小于数组长度的旋转次数
  • rotationGtArrayLength = 8：大于数组长度的旋转次数
  • ltArrayLengthRotation：rotationLtArrayLength的预期结果
  • gtArrayLengthRotation：rotationGtArrayLength的预期结果

初始值如下：

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) {
    // 检查无效输入
    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. 代码解析

我们使用嵌套循环遍历数组两次。外层循环获取要旋转的值：

for (int i = 0; i < k; i++) {
    previous = arr[arr.length - 1];
    // 嵌套循环
}

内层for循环通过临时变量将所有元素移动一位：

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

3.3. 复杂度分析

  • **时间复杂度：O(n×k)*。所有元素在k*次循环中每次移动O(n)步。
  • **空间复杂度：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) {
    // 检查无效输入

    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. 循环替换

我们可以每次将元素替换到其目标位置，但会覆盖原值。因此使用临时变量保存被替换的值，重复此过程直到所有元素都被处理。

5.1. 算法实现

当k=2时，循环替换的逻辑如下图所示：

循环替换示意图

我们从索引0开始，进行2步循环。但这种方法有个问题：可能回到初始位置。此时需要重新开始常规循环。

我们使用count变量跟踪已替换的元素数量，当count等于数组长度时完成旋转：

void cyclicReplacement(int[] arr, int k) {
    // 检查无效输入

    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步替换的元素组：

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

内层do-while循环将值移动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. 算法实现

通过三次反转完成旋转：

  1. 反转整个数组
  2. 反转前k个元素
  3. 反转剩余的(n-k)个元素
void reverse(int[] arr, int k) {
    // 检查无效输入

    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)**。所有元素总共被反转三次。
  • **空间复杂度：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);
}

7. 总结

本文介绍了多种将数组旋转k次的算法。我们从暴力解法开始，逐步深入到更高效的反转法和循环替换法（无需额外空间）。我们讨论了时间复杂度和空间复杂度，并介绍了单元测试和边界情况的处理。

本文所有代码可在GitHub上获取。

原始标题:Rotate Arrays in Java

« 上一篇： Java中float转BigDecimal的几种方式
» 下一篇： Java 18 弃用终结机制详解