题解 | #旋转数组#

旋转数组

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

算法思想一：使用额外数组

解题思路：

可以使用额外的数组来将每个元素放至正确的位置。遍历原数组，将原数组下标为 i 的元素放至新数组下标为 (i+m) mod n （为了防止右移的长度大于数组的长度，所以才有取余）的位置，最后返回新数组即可

图解：

代码展示：

JAVA版本

import java.util.*;


public class Solution {
    /**
     * 旋转数组
     * @param n int整型 数组长度
     * @param m int整型 右移距离
     * @param a int整型一维数组 给定数组
     * @return int整型一维数组
     */
    public int[] solve (int n, int m, int[] a) {
        // write code here
        // 额外新数组
        int[] newArr = new int[n];
        // 遍历原数组
        for (int i = 0; i < n; ++i) {
            // 数组元素旋转
            newArr[(i + m) % n] = a[i];
        }
        return newArr;
    }
}

复杂度分析

时间复杂度 O(n)：其中 n 为数组的长度，遍历数组时间O(n)

空间复杂度O(n)：额外新数组占用空间

算法思想二：数组翻转

解题思路：

该方法基于如下的事实：将数组的元素向右移动 k 次后，尾部 m mod n 个元素会移动至数组头部，其余元素向后移动 m mod n 个位置。
该方法为数组的翻转：翻转算法参考反转链表中的双指针方法 https://blog.nowcoder.net/n/d259b250747b4085bc7975f102d248c4

1、可以先将所有元素翻转，这样尾部的 m mod n 个元素就被移至数组头部，

2、然后再翻转 [0,m mod n−1] 区间的元素

3、最后翻转[m mod n,n−1] 区间的元素即能得到最后的答案。

实例：
以 n=7，m=3 为例进行如下展示：

操作	结果
原始数据	【1，2，3，4，5，6，7】
翻转所有元素	【7，6，5，4，3，2，1】
翻转 [0,m mod n −1] 区间的元素	【5，6，7，4，3，2，1】
翻转 [m mod n, n −1] 区间的元素	【5，6，7，1，2，3，4】

最后返回：【5，6，7，1，2，3，4】

代码展示：

Python版本

class Solution:
    def solve(self , n , m , a ):
        # write code here
        m = m % n
        # 数组反转
        # 翻转全部
        self.reverse(a, 0, n - 1);
        # 再翻转 【0，m-1】
        self.reverse(a, 0, m - 1);
        # 再翻转 【m，n-1】
        self.reverse(a, m, n - 1);
        return a
        
    def reverse(self, nums, start, end):
        # 数组翻转
        while start < end :
            # 双指针遍历翻转
            temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start += 1;
            end -= 1;

复杂度分析

时间复杂度：O(N)，其中 N 为数组的长度。每个元素被翻转两次，一共 N 个元素，因此总时间复杂度为 O(2N)=O(N)。
空间复杂度：O(1)。使用常数级空间变量

算法思想三：数组变换

解题思路：

简单便利的方法：数组直接变换

1、tmp = m mod n，找到右移的距离

2、采用 a[:tmp], a[tmp:] = a[-tmp:],a[:n-tmp] 直接变换

代码展示：

Python版本

class Solution:
    def solve(self , n , m , a ):
        # write code here
        # 获取移动的距离
        tmp = m % n
        # 交换移动数组
        a[:tmp], a[tmp:] = a[-tmp:],a[:n-tmp]
        return a