数组的圆形左移位在java中的n个位置

Question

我试图只使用一个1D阵列,通过n个位置进行数组的圆形左移.我可以在两个数组中完成,但我还没弄明白如何使用它.请提出你的建议

Answer 1

实际上有一个聪明的算法.我们将A用来表示数组,N表示数组大小,并n表示要移位的位置数.在移位之后,您希望i-th元素移动到该((i + n) mode 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具有未移位元素的第三个位置？这也可能表明我们需要保存一个数组以考虑使用过的\ unused元素,并在每次需要查找未使用的元素时执行查找.然而,我们可以再次放松,因为,正如我们很快就会显示,所有的起始位置(我们用表示i,j和k)相邻.这意味着,如果我们从位置开始i,我们接下来会选择i + 1,然后i + 2等等......

3. 可能序列i, f(i), f(f(i)), ...和j, f(j), f(f(j)), ...(在哪里i和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)通过d,我们剩下的余数i,除以一个元素从一组不同的S(j)通过d将使我们能够对不同的余数(j).因此,没有两个集合包含共同元素.有了这个,我们已经确定集合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}第三个断言的分区(没有两个序列包含公共元素).其次,通过集合的定义,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;
    }
}

Answer 2

您可以通过迭代和复制来移动数据，这将是 O(n)。另一种方法是创建一个List包装数组并将其公开为循环移位的实现。这样做的优点是，当get执行 或 迭代时，实际的移位是延迟完成的。