题解 | #旋转数组#

旋转数组

http://www.nowcoder.com/practice/e19927a8fd5d477794dac67096862042

题目描述

一个数组A中存有N（N&gt0）个整数，在不允许使用另外数组的前提下，将每个整数循环向右移M（M>=0）个位置，即将A中的数据由（A0 A1 ……AN-1 ）变换为（AN-M …… AN-1 A0 A1 ……AN-M-1 ）（最后M个数循环移至最前面的M个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

示例1

输入：

6,2,[1,2,3,4,5,6]

返回值：

[5,6,1,2,3,4]

方法一：模拟

解题思路

首先一个很简单明了的想法，因为题目里说的是整体向右移动 M 个位置，那么我们可以先写好每次只向右移动 1 位的操作，再循环 M 次这个操作就可以得到最后的结果。

这里可以做一个小优化，就是如果传入的 M 参数，比数组的长度还要长，我们可以将 M 这个数字缩小来减少循环的次数，也就是减少移动的次数。

如果 M 的值和数组的长度是相等的，那么数组向右整体移动 M 个位置得到的结果是没有变的，之前的数字在什么位置，移动后这个数字仍然在原位置。所以这里可以将 M 对数组的长度取余，只需要移动的次数比数组的长度小即可。

想法很简单，思路也很简单、代码也很简单，那么下面就看看图示和代码示例吧：

图片说明

代码示例

import java.util.*;


public class Solution {
    /**
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param nums int整型一维数组 给定数组
     * @return int整型一维数组
     */
    public int[] solve (int n, int m, int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }

        // 传入的 m 值，可能比数组的长度还大；
        // 此时做一个取模运算即可，减少一些不必要的移动
        int shift = m % nums.length;

        // 数字向右移动一位，这个操作需要进行 shift 次
        for (int i = 0; i < shift; i++) {
            rightShiftOne(nums);
        }

        return nums;
    }


    /**
     * 将 nums 数组的所有数字，往右移动 1 位
     */
    public void rightShiftOne(int[] nums) {
        int len = nums.length;
        // 记录下最后1位的数字
        int temp = nums[len - 1];
        // 除最后1位数字外，所有数字往右移动1位
        for (int i = len - 1; i > 0; i--) {
            nums[i] = nums[i - 1];
        }
        // 将最后1位的数字移动到数组第1位
        nums[0] = temp;
    }
}

复杂度分析

时间复杂度：O( (M%N) * N )

M 为向右移动的位置个数；N 为数组的长度。

首先将数组中所有的数字向右移动 1 位，这里需要遍历完整个数组元素，时间复杂度为 O(N)。

其次这样的操作需要 M % N 次，所以这是一个双重循环遍历，

最后总的时间复杂度为： O( (M%N) * N )

空间复杂度：O(1)

代码里只是声明了有限的几个变量来方便操作，并没有开辟和数据量 N 有关的空间。

所以，空间复杂度为： O(1)。

方法二：反转

解题思路

为了尽可能的减少移动数据的次数，可以采取另外的思路。

可以先自己找几个数组右移 M 个位置，看最后的结果和初始状态有什么区别。可以发现最后的结果可以分为2个部分，这个2个部分一起看的话是没有顺序的，但是分开看，分别集中在这2个部分的各自范围看，可以发现内部是有序的。

这里说的有序无序不是相对于自然数的状态来说的，是相对于原数组的状态来说的，也就是说和原数组的位置顺序区别有没有变化。

就好像一个有序的数组，把他从某一点分割开，再把这2部分调换位置一样。

所以，我们可以通过反转数组来达到同样的结果，因为反转 2 次就还是和原来一样，等于没有反转。

首先我们将整个数组进行反转，然后再看数组中那2个部分的元素分别是多少个，然后再分别反转这些个元素，让这些个元素是有序的，就好像这些个元素是没有变化的。但这样最后的结果就是2个部分一起看是没有顺序的，但分开集中在这2个部分的各自范围看，是有序的，也就达到了我们想要的状态。

另外，为尽可能的减少数据移动的次数，减少空间的开销，在反转的过程中，可以采用双指针的思想，让头部尾部分别进行，一次就交换到位，不用另外开辟一块同样大小的空间。

另外，在反转的时候，如果传入的参数 M 比数组的长度还要大的话，就要做一步取余操作，原因和方法一里阐述的是一样的。

具体的流程及实现请参考下面的图示和代码示例：

图片说明

代码示例

import java.util.*;


public class Solution {
    /**
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param nums int整型一维数组 给定数组
     * @return int整型一维数组
     */
    public int[] solve (int n, int m, int[] nums) {
        if (nums == null || nums.length == 0) {
            return null;
        }

        // 数组的长度
        int len = nums.length;
        // 右移的位数可能会比长度还要大，取个模就好了
        int shift = m % len;

        // 反转整个数组
        reverse(nums, 0, len - 1);
        // 反转数组的前 shift 个数
        reverse(nums, 0, shift - 1);
        // 反转数组剩余数字
        reverse(nums, shift, len - 1);

        return nums;
    }


    /**
     * 将数字 nums[left...right] 范围上的数字反转
     */
    public void reverse(int[] nums, int left, int right) {
        if (left >= right) {
            return;
        }

        // 用左右指针，相互交换即可
        int times = (right - left + 1) / 2;
        for (int i = 0; i < times; i++) {
            swap(nums, left++, right--);
        }
    }

    /**
     * 将 nums[i] ， nums[j] 这两个数字交换
     */
    public void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}