旋转阵列

Question

我正在尝试旋转一个数组,以便给定一个数字和一个数组,然后按该数量旋转数组.IE:

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).

现在,因为我的解决方案是非常可怕的,我会还发布取自下面的代码在这里

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风格实现,它比我的运行速度更快,使用三个反转的基本思想,你可以实现内联移位.

正如这里所说,

诀窍是做三个反向操作.一个用于整个字符串,一个从索引0到k-1,最后索引k到n-1.奇怪的是,这将产生正确的旋转阵列,没有任何额外的空间!(当然,您需要一个临时变量进行交换).

我还没有在我链接的博客上验证这个属性,所以我会发布一些看起来有效但我自己从未测试过的...