JAVA数据结构 设计一个算法，将含有n个整数元素的数组a[0..n-1]循环右移m位，要求算法的空间复杂度为O(1)

JAVA设计一个算法，将含有n个整数元素的数组a[0..n-1]循环右移m位，要求算法的空间复杂度为O(1)

public static void rotateArray(int[] a, int m) {
    int n = a.length;
    m %= n;

    reverse(a, 0, n - m - 1);
    reverse(a, n - m, n - 1);
    reverse(a, 0, n - 1);
}

private static void reverse(int[] a, int start, int end) {
    while (start < end) {
        int temp = a[start];
        a[start++] = a[end];
        a[end--] = temp;
    }
}

可以采用三次翻转的方式来实现将数组a循环右移m位。

具体的步骤如下：

1、将a[0..n-m-1]和a[n-m..n-1]分别进行翻转；
2、将整个数组a[0..n-1]进行翻转；
3、将a[0..m-1]和a[m..n-1]分别进行翻转。
这样就能实现将数组a循环右移m位，而且空间复杂度为O(1)。

• 请看👉 ：已知一个整数数组A[n]，写出算法实现将奇数元素放在数组的左边，将偶数放在数组的右边。要求时间复杂度为O(n)。
• 除此之外, 这篇博客: 算法之给定一个n*m的格子或棋盘，如何计算从左上角走到右下角的走法总数？（Java）中的 5.非递归求法，时间复杂度O(n) 部分也许能够解决你的问题, 你可以仔细阅读以下内容或跳转源博客中阅读:
  

• 其实就是一个排列组合计算，可以用排列组合公式来进行求值。C(n+m,n)下项为n+m，上项为n。
  要注意的就是阶乘算起来容易过大，int接收不了的时候可以及时换成double来接收。

      private int totalMethod2(int n, int m) {
          int sum = 0;
          int sum1 = 1;
          int sum2 = 1;
  
          if (n >= m){
              for (int i = n+1; i <= (m+n); i++) {
                  sum1 = sum1 * i;
              }
  
              for (int i = 1; i <= m; i++) {
                  sum2 = sum2 * i;
              }
  
          }else {
              for (int i = m+1; i <= (m+n); i++) {
                  sum1 = sum1 * i;
              }
  
              for (int i = 1; i <= n; i++) {
                  sum2 = sum2 * i;
              }
          }
  
          sum = sum1 / sum2;
  
          return sum;
      }