leetcode 189. 旋转数组

Myth丶恋晨 2022-01-20 11:59 222阅读 0赞

# 189. 旋转数组 #

> 难度：简单
> 
> 题库地址：[leetcode-cn.com/problems/ro…][leetcode-cn.com_problems_ro]

## 1. 题目描述 ##

给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。

示例 1:

输入: [1,2,3,4,5,6,7] 和 k = 3
    输出: [5,6,7,1,2,3,4]
    解释:
    向右旋转 1 步: [7,1,2,3,4,5,6]
    向右旋转 2 步: [6,7,1,2,3,4,5]
    向右旋转 3 步: [5,6,7,1,2,3,4]
    复制代码

示例 2:

输入: [-1,-100,3,99] 和 k = 2
    输出: [3,99,-1,-100]
    解释: 
    向右旋转 1 步: [99,-1,-100,3]
    向右旋转 2 步: [3,99,-1,-100]
    复制代码

说明:

*  尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
 *  要求使用空间复杂度为 O(1) 的原地算法。

## 2. 解题思路 ##

英文版的有答案：[leetcode.com/problems/ro…][leetcode.com_problems_ro]

这里记录一下第4种方法的理解：**Approach \#4 Using Reverse \[Accepted\]**

**假设对长度为 n 的数组，进行 k 次旋转。**

首先要找到**最终有效**的次数，因为旋转的循环的，当对数组进行 n 次旋转时，相当于没有对数组进行操作，同时该方法必须先找到最终有效次数，否则没法对数组进行镜像操作。

为什么在不同位置采用三次镜像操作就能实现数组的 k 次旋转，连同答案和自己的理解整理为如下：

1.  先计算 ![k][] 的有效次数，因为旋转是循环进行的，像自行车链条一样，当元素旋转一整圈即：![k = n][k _ n] 时，所有元素回到了原来的位置，所以 ![k][] 次旋转的有效次数为 ![k \\% n][k _ n 1]。
2.  我们将数组以 ![n][] 为边界拆分成两部分看待，前 ![n-k][] 个元素部分：![S\_1 = \\\{t\_1,t\_2,...,t\_\{n-k\}\\\}][S_1 _ _t_1_t_2_..._t_n-k] 和 后 ![n][] 个元素部分 ![S\_2 = \\\{t\_\{n-k+1\},t\_\{n-k+2\},...,t\_n\\\}][S_2 _ _t_n-k_1_t_n-k_2_..._t_n]，为什么以 ![k][] 为分界点呢？因为对数组进行 ![k][] 次旋转后，![S\_1][S_1] 和 ![S\_2][S_2] 将互换位置。 如数组：![\\\{1,2,3,4,5,6\\\}][1_2_3_4_5_6]，长度 ![n = 6][n _ 6]，进行 ![k=2][k_2] 次旋转，对应 ![S\_1 = \\\{1, 2, 3, 4\\\}][S_1 _ _1_ 2_ 3_ 4]，![S\_2 = \\\{5,6\\\}][S_2 _ _5_6]，旋转结束后得到数组： ![S\_2 = \\\{5, 6\\\}][S_2 _ _5_ 6] ，![S\_1 = \\\{1, 2, 3, 4\\\}][S_1 _ _1_ 2_ 3_ 4]
3.  为了实现将 ![S\_1][S_1] 和 ![S\_2][S_2] 位置互换，这里采用将整个数组镜像的策略。 原元素：![\\\{1,2,3,4,5,6\\\}][1_2_3_4_5_6] 镜像后：![\\\{6, 5, 4, 3, 2, 1\\\}][6_ 5_ 4_ 3_ 2_ 1]
4.  对数组进行镜像操作后，虽然 ![S\_1][S_1] 和 ![S\_2][S_2] 位置互换，但是其**内部元素也被镜像了**，为了将 ![S\_1][S_1] 和 ![S\_2][S_2] 内部元素的顺序恢复，对 ![S\_1][S_1] 和 ![S\_2][S_2] 再分别进行一次镜像。
    
    举例如下原数组：![\\\{1,2,3,4,5,6\\\}][1_2_3_4_5_6] 镜像前： ![S\_1 = \\\{1, 2, 3, 4\\\}][S_1 _ _1_ 2_ 3_ 4] ， ![S\_2 = \\\{5,6\\\}][S_2 _ _5_6] 镜像后：![S\_2 = \\\{6,5\\\}][S_2 _ _6_5] ，![S\_1 = \\\{4, 3, 2, 1\\\}][S_1 _ _4_ 3_ 2_ 1] 对 ![S\_1][S_1] 和 ![S\_2][S_2] 分别进行一次镜像后得到的最终结果：![S\_2 = \\\{5, 6\\\}][S_2 _ _5_ 6] ，![S\_1 = \\\{1, 2, 3, 4\\\}][S_1 _ _1_ 2_ 3_ 4] 最终答案：![\\\{5, 6, 1, 2, 3, 4\\\}][5_ 6_ 1_ 2_ 3_ 4]
    
    算法思想再精简一点如下：
    
    1.  对数组以 ![k][] 划分成两部分，分为前 ![n-k][] 个元素部分，和后 ![k][] 个部分，这样划分的目的是旋转 ![k][] 次后这两部分正好位置互换。
    2.  为了实现这种位置互换需要将数组镜像
    3.  镜像虽然将两部分数据整体的位置转换了过来，但是两部分数组内部数据顺序错误，需要对两部分数组分别镜像

Java实现：

class Solution {
        public void rotate(int[] nums, int k) {
            if (nums == null || nums.length < 2) {
                return;
            }
            // 计算有效旋转次数
            k %= nums.length;
            // 对整个数组镜像，使 S2 和 S1 位置互换
            reverse(nums, 0, nums.length - 1);
            // 对 S2 镜像处理，使其内部元素顺序恢复
            reverse(nums, 0, k - 1);
            // 对 S1 镜像处理，使其内部元素顺序恢复
            reverse(nums, k, nums.length - 1);
        }
    
        private void reverse(int[] nums, int start, int end) {
            while (start < end) {
                int temp = nums[end];
                nums[end] = nums[start];
                nums[start] = temp;
                start++;
                end--;
            }
        }
    }
    复制代码

[leetcode-cn.com_problems_ro]: https://link.juejin.im?target=https%3A%2F%2Fleetcode-cn.com%2Fproblems%2Frotate-array%2F
[leetcode.com_problems_ro]: https://link.juejin.im?target=https%3A%2F%2Fleetcode.com%2Fproblems%2Frotate-array%2Fsolution%2F
[k]: /images/20220120/1369ea87e5a8443987da31afbd1297fe.png
[k _ n]: /images/20220120/1369ea87e5a8443987da31afbd1297fe.png%20%3D%20n
[k _ n 1]: /images/20220120/1369ea87e5a8443987da31afbd1297fe.png%20%5C%25%20n
[n]: https://juejin.im/equation?tex=n
[n-k]: https://juejin.im/equation?tex=n-k
[S_1 _ _t_1_t_2_..._t_n-k]: https://juejin.im/equation?tex=S_1%20%3D%20%5C%7Bt_1%2Ct_2%2C...%2Ct_%7Bn-k%7D%5C%7D
[S_2 _ _t_n-k_1_t_n-k_2_..._t_n]: /images/20220120/d1960af4498145f9813789b514badb51.png%20%3D%20%5C%7Bt_%7Bn-k%2B1%7D%2Ct_%7Bn-k%2B2%7D%2C...%2Ct_n%5C%7D
[S_1]: https://juejin.im/equation?tex=S_1
[S_2]: /images/20220120/d1960af4498145f9813789b514badb51.png
[1_2_3_4_5_6]: https://juejin.im/equation?tex=%5C%7B1%2C2%2C3%2C4%2C5%2C6%5C%7D
[n _ 6]: https://juejin.im/equation?tex=n%20%3D%206
[k_2]: /images/20220120/1369ea87e5a8443987da31afbd1297fe.png%3D2
[S_1 _ _1_ 2_ 3_ 4]: https://juejin.im/equation?tex=S_1%20%3D%20%5C%7B1%2C%202%2C%203%2C%204%5C%7D
[S_2 _ _5_6]: /images/20220120/d1960af4498145f9813789b514badb51.png%20%3D%20%5C%7B5%2C6%5C%7D
[S_2 _ _5_ 6]: /images/20220120/d1960af4498145f9813789b514badb51.png%20%3D%20%5C%7B5%2C%206%5C%7D
[6_ 5_ 4_ 3_ 2_ 1]: /images/20220120/a9d31f9610db46abba6c3b3c6a6f2774.png
[S_2 _ _6_5]: /images/20220120/d1960af4498145f9813789b514badb51.png%20%3D%20%5C%7B6%2C5%5C%7D
[S_1 _ _4_ 3_ 2_ 1]: https://juejin.im/equation?tex=S_1%20%3D%20%5C%7B4%2C%203%2C%202%2C%201%5C%7D
[5_ 6_ 1_ 2_ 3_ 4]: /images/20220120/da1203c67e864b87a23acdbe7b66cc10.png