数组旋转问题：空间复杂度O(1)的解法

数组旋转是算法中的经典问题：给定一个数组，将数组元素向右（或向左）旋转k个位置。例如，数组 [1,2,3,4,5,6,7]向右旋转3位后变为 [5,6,7,1,2,3,4]。

最直观的解法是使用额外数组存储旋转后的结果，但这需要O(n)的额外空间。本文将深入探讨三种空间复杂度O(1)的原地算法，让你在不使用额外数组的情况下优雅地解决这个问题。

方法一：环状替换法

这是最巧妙的O(1)空间解法，通过数学计算直接确定每个元素的最终位置。

public class ArrayRotation {
    
    /**
     * 环状替换法实现数组旋转
     * @param nums 待旋转数组
     * @param k 旋转步数
     */
    public void rotateByCyclicReplacement(int[] nums, int k) {
        if (nums == null || nums.length == 0 || k % nums.length == 0) {
            return;
        }
        
        int n = nums.length;
        k = k % n;  // 处理k大于数组长度的情况
        int count = 0;  // 记录已移动的元素个数
        
        for (int start = 0; count < n; start++) {
            int current = start;
            int prev = nums[start];
            
            do {
                int next = (current + k) % n;
                int temp = nums[next];
                nums[next] = prev;
                prev = temp;
                current = next;
                count++;
            } while (start != current);
        }
    }
}

算法思路：

每个元素都会移动到(当前位置 + k) % n的位置
但直接移动会覆盖目标位置的元素，所以需要保存被覆盖的元素
从起始位置开始，沿着替换链一直移动，直到回到起始位置
如果还有未移动的元素，从下一个位置开始新的循环

时间复杂度：O(n) – 每个元素只移动一次

空间复杂度：O(1) – 只使用了几个临时变量

方法二：三次反转法

这种方法通过三次反转操作实现旋转，代码简洁且易于理解。

public class ArrayRotation {
    
    /**
     * 三次反转法实现数组旋转
     * @param nums 待旋转数组
     * @param k 旋转步数
     */
    public void rotateByThreeReversals(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return;
        }
        
        int n = nums.length;
        k = k % n;
        
        // 第一步：反转整个数组
        reverse(nums, 0, n - 1);
        // 第二步：反转前k个元素
        reverse(nums, 0, k - 1);
        // 第三步：反转剩余元素
        reverse(nums, k, n - 1);
    }
    
    /**
     * 辅助方法：反转数组中指定范围的元素
     * @param nums 数组
     * @param start 起始索引
     * @param end 结束索引
     */
    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}

算法原理：

以数组[1,2,3,4,5,6,7]，k=3为例：

整体反转：[7,6,5,4,3,2,1]
反转前3个：[5,6,7,4,3,2,1]
反转后4个：[5,6,7,1,2,3,4]

时间复杂度：O(n) – 每个元素被访问两次

空间复杂度：O(1) – 原地操作

方法三：块交换法（递归实现）

这种方法将数组分成两块，通过递归交换实现旋转。

public class ArrayRotation {
    
    /**
     * 块交换法实现数组旋转（递归版本）
     * @param nums 待旋转数组
     * @param k 旋转步数
     */
    public void rotateByBlockSwap(int[] nums, int k) {
        if (nums == null || nums.length == 0) {
            return;
        }
        
        k = k % nums.length;
        blockSwapRecursive(nums, 0, nums.length - k, nums.length, k);
    }
    
    /**
     * 递归块交换
     * @param nums 数组
     * @param startA A块的起始索引
     * @param startB B块的起始索引
     * @param size 当前处理的块大小
     * @param k 旋转距离
     */
    private void blockSwapRecursive(int[] nums, int startA, int startB, int size, int k) {
        if (size == 0 || k == 0 || k == size) {
            return;
        }
        
        if (k == size - k) {
            // 两块大小相等，直接交换
            swapBlocks(nums, startA, startB, k);
            return;
        }
        
        if (k < size - k) {
            // A块较小
            swapBlocks(nums, startA, startB, k);
            // 递归处理剩余部分
            blockSwapRecursive(nums, startA, startB + k, size - k, k);
        } else {
            // B块较小
            swapBlocks(nums, startA, startB, size - k);
            // 递归处理剩余部分
            blockSwapRecursive(nums, startA + (size - k), startB, k, 2 * k - size);
        }
    }
    
    /**
     * 交换两个等长的块
     */
    private void swapBlocks(int[] nums, int startA, int startB, int size) {
        for (int i = 0; i < size; i++) {
            int temp = nums[startA + i];
            nums[startA + i] = nums[startB + i];
            nums[startB + i] = temp;
        }
    }
}

性能对比与选择建议

方法	时间复杂度	空间复杂度	优点	缺点
环状替换	O(n)	O(1)	每个元素只移动一次	逻辑较复杂
三次反转	O(n)	O(1)	实现简单，容易理解	每个元素访问两次
块交换	O(n)	O(1)	递归思路清晰	递归有栈空间开销

选择建议：

面试或竞赛：推荐三次反转法，代码简洁，容易讲解
生产环境：根据具体场景选择，三次反转法通常足够
学习理解：建议都实现一遍，理解不同思路

测试示例

public class TestArrayRotation {
    public static void main(String[] args) {
        ArrayRotation rotation = new ArrayRotation();
        
        // 测试用例1
        int[] nums1 = {1, 2, 3, 4, 5, 6, 7};
        rotation.rotateByThreeReversals(nums1, 3);
        System.out.println("三次反转法结果: " + Arrays.toString(nums1));
        // 输出: [5, 6, 7, 1, 2, 3, 4]
        
        // 测试用例2: k大于数组长度
        int[] nums2 = {-1, -100, 3, 99};
        rotation.rotateByCyclicReplacement(nums2, 6);  // 实际旋转2位
        System.out.println("环状替换法结果: " + Arrays.toString(nums2));
        // 输出: [3, 99, -1, -100]
    }
}

总结

数组旋转问题虽然简单，但其中蕴含的算法思想却很深刻。三种O(1)空间复杂度的解法各有特点：

环状替换法展示了如何通过数学计算优雅处理循环依赖
三次反转法体现了”分而治之”的思想，将复杂问题分解为简单操作
块交换法展示了递归思维在数组操作中的应用

理解这些解法不仅能帮助你在面试中脱颖而出，更能提升你解决实际问题的算法思维。记住，优秀的算法不仅仅是正确的，更应该是高效且优雅的。

方法一：环状替换法

方法二：三次反转法

方法三：块交换法（递归实现）

性能对比与选择建议

测试示例

总结

相关文章