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

Question

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

Answer 1

实际上有一个聪明的算法。我们将使用 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))), ...)。就是这样。但是在我们可以实现这样的算法之前，或者甚至在我们确定这是否确实是一个好的算法之前，我们需要回答几个问题:

假设我们遍历位置 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 和 k 表示)都是相邻的。这意味着，如果我们从位置 i 开始，我们接下来选择 i + 1 ，然后 i + 2 ，等等……

可能是序列 i, f(i), f(f(i)), ...和 j, f(j), f(f(j)), ... (其中 i 和 j 不同)包含共同元素？如果他们这样做将意味着该算法是无用的，因为它可以将同一个元素移动两次 - 导致它最终处于错误的位置。那么答案(当然)是它们不能包含公共(public)元素。我们将说明原因。

让我们表示 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)来自 d ，我们只剩下余数 i ，并将元素从不同的集合中划分 S(j)来自 d会给我们留下不同的余数( j )。因此，没有两个集合包含一个公共(public)元素。有了这个，我们已经建立了集合 S(0),...,S(d - 1)形成 {0,...,N - 1}的分区

现在，对于每个 i = 0,...,d - 1 ，我们将定义集合 T(i)如 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

因此， x也在 S(i) .同样，如果我们取一些 y来自 S(i)我们观察到，对于一些 k :

y = kd + i

自 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

因此， y也在 T(i) .我们得出的结论是 T(i) = S(i) .从这个事实我们可以很容易地展示我们之前的断言。首先，由于集合形成了 {0,...,N - 1} 的分区。满足第三个断言(没有两个序列包含公共(public)元素)。二、由集合的定义 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;
    }
}