java - 旋转数组

Question

我正在尝试旋转一个数组，以便给定一个数字和一个数组，将数组旋转该数量。即:

abcdefgh

给定 3:

fghabcde

在不使用额外数据结构/最小空间的情况下，最好的方法是什么？

这是一个函数头:

public static char[] rotateString(char[] s, int rotateAmount){

}

Answer 1

首先，我会做一个很大的假设，“更好”意味着“我不想要任何/尽可能少的新数据结构”。

如果是这种情况，那么最简单的解决方案就是最好的，因为我不需要按时间优化。我知道其他解决方案要优雅得多，我发布它只是因为我读到的问题是“确保它在空间方面是最小的”。

private static String rotate( final char[] a, final int n ) {
    for(int i = 0; i < n; i++) {
        char tmp = a[a.length-1];
        for(int j = a.length-1; j >= 0; j--) {
            a[j] = j == 0 ? tmp : a[(j-1+a.length)%a.length];
        }
    }
    return new String(a);
}

所以我很快就解决了这个问题。基本上，我只是按 1 的长度进行旋转，直到我旋转了 n 次。要优化它，您可能可以采用 gcd(n, a.length)。

现在，由于我的解决方案非常糟糕，我还将发布以下摘自 here 的代码

void reverse_string(char* str, int left, int right) {
  char* p1 = str + left;
  char* p2 = str + right;
  while (p1 < p2) {
    char temp = *p1;
    *p1 = *p2;
    *p2 = temp;
    p1++;
    p2--;
  }
}

void rotate(char* str, int k) {
  int n = strlen(str);
  reverse_string(str, 0, n-1);
  reverse_string(str, 0, k-1);
  reverse_string(str, k, n-1);
}

我假设这是一个运行速度比我的更快的 C 风格实现，使用一个基本思想，即通过三个反向，您可以实现内联移位。

正如这里所说，

The trick is to do three reverse operation. One for the entire string, one from index 0 to k-1, and lastly index k to n-1. Magically, this will yield the correct rotated array, without any extra space! (Of course, you need a temporary variable for swapping).

我还没有在我链接到的博客上验证这个属性，所以我会对它发表一些怀疑，它似乎可以工作，但我自己从未测试过......