题目

描述

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

方法一

思路

旋转数组，可以一步一步的旋转数组，当右移距离为m时，可以分为m次右移数组。

具体步骤

• 1.将数组中的所有数向右移动一步，即a[index] = a[index-1],a[0] = a[a.length-1];
• 循环步骤1;M次
• 代码如下：

  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) {
     // 移m步，所以循环m次
     for (int i = 0; i < m; ++i){
         rotate(a);
     }
     return a;
  }
  // 旋转函数，步长为1
  private void rotate(int[] a){
     int temp = a[0];
     // 数组中的每个数都往前移一位，越界则模数组的长度
     for(int i = 1; i < a.length; ++i){
         int index = (i+1)%a.length;
         int tmp = a[i];
         a[i] = temp;
         temp = tmp;
     }
     a[0] = temp;
  }
  }

• 时间复杂度：，一步一步的移动，每一次移动都是n，总共移动m次，所以为；
• 空间复杂度：，常数级空间复杂度。

  方法二

  思路

• 方法一是一步一步的右移数组，导致时间复杂度为，那么为了减少时间复杂度，可以使用反转数组的思想。
• 依次将(0,n-m-1),(n-m,n-1),(0,n-1)进行反转，即为右移m步后的数组。

  具体步骤

• 参考下图的栗子：
  
• 代码如下：

  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) {
        // 三次反转
        // 1 2 3 4 5 6
        // 4 3 2 1 5 6
        // 4 3 2 1 6 5
        // 5 6 1 2 3 4
        // n-m至n-1的数据反转
        reverse(a,n-m,n-1);
         // 0至n-m-1的数据反转
        reverse(a,0,n-m-1);
        // 全员反转
        reverse(a,0,n-1);
        return a;
    }
    // 反转数组
    private void reverse(int[] a,int start,int end){
        while(start < end){
            int temp = a[start];
            a[start] = a[end];
            a[end] = temp;
            ++start;
            --end;
        }
    }
  }

• 时间复杂度：，全局反转，最大为。
• 空间复杂度：，常数级空间复杂度。