BM97 旋转数组

题目描述

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

数据范围：0<n≤100，0≤m≤1000
进阶：空间复杂度 O(1)，时间复杂度 O(n)

示例1
输入：
6,2,[1,2,3,4,5,6]
返回值：
[5,6,1,2,3,4]

示例2
输入：
4,0,[1,2,3,4]
返回值：
[1,2,3,4]

备注：
(1<=N<=100,M>=0)

解题思路

1.此题实际上很简单，如果采用辅助数组的话，那么只需要去平移就可以了
2.但是题目要求空间复杂度为O（1），所以我们要考虑原地移动，那么明显需要找寻一下规律
3.步骤

• step 1：因为m可能大于n，因此需要对n取余，因为每次长度为n的旋转数组相当于没有变化。
• step 2：第一次将整个数组翻转，得到数组的逆序，它已经满足了右移的整体出现在了左边。
• step 3：第二次就将左边的m个元素单独翻转，因为它虽然移到了左边，但是逆序了。
• step 4：第三次就将右边的n−m个元素单独翻转，因此这部分也逆序了。

实践代码

import java.security.spec.ECPrivateKeySpec;
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) {
        reverseA(a, 0, n - 1);
        reverseA(a, 0, m % n - 1);
        reverseA(a, m % n, n - 1);
        return a;
    }

    private void reverseA(int[] a, int i, int j) {
        while (i < j) {
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;
            i++;
            j--;
        }
    }

}