java中数组循环左移n个位置

我正在尝试仅使用单个一维数组将数组循环左移 n 个位置。我可以在两个数组中完成它，但我还没有弄清楚如何使用一个数组来完成它。请提出您的建议

实际上有一个聪明的算法可以做到这一点。我们将使用A来表示数组，N表示数组大小，以及n表示要移动的位置数。轮班后您希望i-th元素移动到((i + n) mod N)-th位置，因此我们可以通过以下映射定义新位置：

f(j) := (j + n) mod N  (j = 0,...,N - 1)

该算法背后的总体思想是这样的：我们不想移动元素超过必要的范围，因此理想情况下，我们希望在第一次尝试时将每个元素简单地放置在正确的（移动的）位置。假设我们从位置处的元素开始i。我们想要做的是将元素移动到位置i定位f(i)，但是我们会覆盖该位置的元素，所以我们需要首先保存该位置的元素f(i)然后执行转变。一旦我们移动了第一个元素，我们就需要选择另一个元素来移动。由于我们想要节省空间，因此明显的候选者是我们刚刚保存的元素（位于位置的元素f(i)）。像以前一样，我们将元素保存在位置f(f(i))然后将我们保存的元素复制到该位置。我们不断重复这个过程（遍历位置i, f(i), f(f(i)), f(f(f(i))), ...）直到我们到达一个我们已经移动的元素（我们保证会这样做，因为位置有限）。如果我们遍历了所有元素，那么我们就完成了，如果没有，那么我们选择另一个元素（尚未移动），比如在位置j，然后重复该过程（经过j, f(j), f(f(j)), f(f(f(j))), ...）。就是这样。但在我们实现这样的算法之前，或者甚至在我们决定这是否确实是一个好的算法之前，我们需要回答几个问题：

1. 假设我们迭代位置i, f(i), f(f(i)), ...。我们如何知道我们到达的位置已经发生了变化？我们需要保存我们经过的每个位置吗？如果这样做，那么这意味着我们需要保存一个大小为 N 的数组（以覆盖所有位置），并且每次移动元素时我们还需要执行查找。这将使算法效率极低。幸运的是，这不是必需的，因为序列i, f(i), f(f(i)), ...必须在位置处缠绕自身i，所以我们只需要等到到达那个位置即可。我们可以如下证明这个断言：假设我们遇到的第一个重复元素不是i。那么我们必须有两个不同的元素，当移动时会到达相同的位置 - 这是一个矛盾。

2. 说我们完成了i, f(i), f(f(i)), ...，但仍然有元素保持不变（我们可以通过计算我们移动了多少个元素来判断）。现在我们如何找到职位j含有这样的元素？而且，一旦我们完成了第二次迭代（经历j, f(j), f(f(j)), ...）我们如何找到第三个位置k与一个未移动的元素？等等......这也可能表明我们需要保存一个数组来说明已使用的\未使用的元素，并在每次需要查找未使用的元素时执行查找。然而，我们可以再次放松，因为，正如我们很快将展示的，所有起始位置（我们用i, j and k) 是相邻的。这意味着，如果我们从位置开始i，我们接下来选择i + 1， 进而i + 2， 等等…

3. 可能是序列i, f(i), f(f(i)), ... and j, f(j), f(f(j)), ... (wherei and j不同）包含共同元素？如果他们这样做，就意味着该算法毫无用处，因为它可能会将同一元素移动两次 - 导致它最终处于错误的位置。那么答案（当然）是它们不能包含共同元素。我们将展示原因。

让我们表示d := gcd(N, n)。对于每一个整数：i = 0,...,d - 1我们定义以下集合：

S(i) := { kd + i | k = 0,...,N/d - 1}

很容易看出集合S(0),...,S(d - 1)一起覆盖集合{0,...,N - 1}。我们还观察到，当划分集合中的元素时S(i) by d，我们剩下余数i，并从不同的集合中划分一个元素S(j) by d会给我们留下不同的余数（j）。因此，没有两个集合包含公共元素。至此，我们确定了集合S(0),...,S(d - 1)形成一个分区{0,...,N - 1}

现在，对于每一个i = 0,...,d - 1，我们将定义集合T(i) as i, f(i), f(f(i)), ...。根据定义f我们可以写T(i)如下：

T(i) = {(kn + i) mod N | k is an integer}

我们观察到，如果x是一个元素T(i)，那么我们可以写一些k:

x = (kn + i) mod N = (k(n/d)d + i) mod N

让我们表示z := k(n/d) mod N/d，然后乘以d， 我们有：

kn mod N = zd

因此：

x = (kn + i) mod N = zd + i

Thus, x也在S(i)。同样，如果我们采取一些y from S(i)我们观察到对于某些k:

y = kd + i

Since gcd(n/d, N/d) = 1存在一个q这样q(n/d) mod N/d = 1（模逆），因此我们可以写（乘以kd):

kd = kqn mod N

因此：

y = kd + i = ((kq)n + i) mod N

Thus, y也在T(i)。我们的结论是T(i) = S(i)。从这个事实我们可以很容易地证明我们之前的断言。首先，由于这些集合形成了一个分区{0,...,N - 1}第三个断言（没有两个序列包含公共元素）得到满足。二、由集合的定义S(i)我们可以带任何一组d中的相邻元素{0,...N - 1}并且它们中的每一个都会被放置在不同的集合中。这满足了第二个断言。

这意味着什么是我们可以旋转所有元素的位置0, d, 2d, ..., (N/d - 1)d通过简单地替换位置处的元素n mod N元素位于位置0, 位置处的元素2n mod N元素位于位置n mod N，依此类推……直到我们返回到位置上的元素0（我们确信这将会发生）。这是一个伪代码示例：

temp <- A[0]
j <- N - (n mod N)
while j != 0 do
    A[(j + n) mod N] <- A[j];
    j <- (j - n) mod N
A[n mod N] <- temp;

这涵盖了整个集合S(0)。覆盖其余的集合，即S(1), … ,S(d-1)，我们将简单地迭代每个集合，就像我们对第一个集合所做的那样：

for i <- 0 to d - 1
    temp <- A[i]
    j <- N - ((n - i) mod N)
    while j != i do
        A[(j + n) mod N] <- A[j];
        j <- (j - n) mod N
    A[(i + n) mod N] <- temp;

请注意，虽然我们有两个嵌套循环，但每个元素仅移动一次，并且我们使用O(1)空间。 Java 中的实现示例：

public static int gcd(int a, int b) {
    while(b != 0) {
        int c = a;
        a = b;
        b = c % a;
    }
    return a;
}

public static void shift_array(int[] A, int n) {
    int N = A.length;
    n %= N;
    if(n < 0)
        n = N + n;
    int d = gcd(N, n);
    for(int i = 0; i < d; i++) {
        int temp = A[i];
        for(int j = i - n + N; j != i; j = (j - n + N) % N)
            A[(j + n) % N] = A[j];
        A[i + n] = temp;
    }
}