三次反转法解决轮转数组问题 | IT宅-帅旋的专业知识分享

题目：189. 轮转数组^[1]

如果您已经有思路了，或者是N刷了，可以先自己写一遍。

题目分析

这道题可以这样表述：给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

例如：

输入: nums = [1,2,3,1,1,1,1], k = 3
输出:  [1,1,1,1,1,2,3]

解题思路

观察以上案例，可以发现，通过三次反转法，可以达到我们需要的结果。为方便观察，我们假设数组是这样的：

nums = “=====>—>”; k = 3，假设k=3的位置刚好是第一个箭头结束的位置

result = “—>=====>”;

三次反转法：

• 反转整个数组：<---<=====；
• 反转第一段：---><=====；
• 反转第二段：--->=====>;

这种方法的好处是只需要线性时间即可完成，时间复杂度为 O(n)，且不需要使用额外的存储空间。

数组反转是一种常用的数组操作技巧，它不仅可以用于解决数组轮转问题，也常用于其他需要调整数组元素位置的场景。

这种方法的优点是它的空间复杂度为 O(1)，即不需要额外的存储空间，同时它的时间复杂度为 O(n)，因为每个元素只被移动有限次数。通过巧妙地利用数组反转，可以高效地解决数组轮转问题。

Java解法

下面是使用Java语言的解法：

public class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length; // 如果k大于数组长度，取模避免多余的旋转
        reverse(nums, 0, nums.length - 1); // 反转整个数组
        reverse(nums, 0, k - 1); // 反转前k个元素
        reverse(nums, k, nums.length - 1); // 反转剩下的元素
    }
    
    // 辅助方法：用于反转数组从start到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--;
        }
    }
}

References

---

1. 189. 轮转数组. Retrieved from https://leetcode.cn/problems/rotate-array/ ↩︎