如何对整数循环数组执行左移？

Question

是否存在对整数循环数组执行左移的现有方法？

具体来说，给定一个包含 4 个项目 {1,2,3,4} 且移位量为 2 的数组，我想要一种将前两个字母移到数组后面的方法，使得它看起来像这样：{3,4,1,2}。

该算法可以将圆形数组移动一位吗？

algShiftByOne(Array)
{
  temp=array[0];
  i=1
  while(i < Array.length - 1) // Loop from 1 up to array.length == last index
  {
    // If there is no exception i assume it copies value from
    // initial array starting from 1 up to array.length
    Array[i - 1] = Array[i];
    i++;
  }
 Array[Array.length]=temp;
}

Answer 1

假设您要按 n 移位：

1. 复制名为 的数组中的前 n 个元素，例如 tempNumbers
2. 对于从 n 到的每个元素最后一个，向左移动 n
3. 将 tempNumbers 中的元素复制到原始数组的末尾

Answer 2

为什么不使用循环（双向）链表？在这种情况下，您只需更改“起始指针”即可。

Answer 3

这是一些伪代码来完成您想要的操作。

Array shift(Array a, int shiftLength) {
    Array b;

    for(i = shiftLength; i < a.size(); i++)
        b.add(a.at(i));

    for(i = 0; i < shiftLength; i++)
        b.add(a.at(i));

    return b;
}

Answer 4

这会将数组向左移动一位。

int[] a = new int[] { 1, 2, 3, 4, 5 };
int[] b = new int[a.length];
System.arraycopy(a, 1, b, 0, a.length - 1);
b[a.length - 1] = a[0];
// b = {2,3,4,5,1}
// edit
a = b;

Answer 5

public static void shift(int[] arr, int offs) {
    // e.g. arr = 1,2,3,4,5,6,7,8,9; offs = 3
    offs %= arr.length;
    offs = offs < 0 ? arr.length + offs : offs;

    if (offs > 0) {
        // reverse whole array (arr = 9,8,7,6,5,4,3,2,1)
        for (int i = 0, j = arr.length - 1; i < j; i++, j--)
            swap(arr, i, j);
        // reverse left part (arr = 7,8,9,6,5,4,3,2,1)
        for (int i = 0, j = offs - 1; i < j; i++, j--)
            swap(arr, i, j);
        // reverse right part (arr = 7,8,9,1,2,3,4,5,6)
        for (int i = offs, j = arr.length - 1; i < j; i++, j--)
            swap(arr, i, j);
    }
}

private static void swap(int[] arr, int i, int j) {
    int tmp = arr[i];
    arr[i] = arr[j];
    arr[j] = tmp;
}

Answer 6

这是我的尝试...（这里是 ideone.com 演示）

import java.util.Arrays;

public class Test {

    public static void circularShiftLeft(int[] arr) {
        if (arr.length == 0)
            return;

        int first = arr[0];
        System.arraycopy(arr, 1, arr, 0, arr.length - 1);
        arr[arr.length - 1] = first;
    }

    public static void main(String[] arg) {
        int[] arr = { 1, 2, 3, 4 };
        System.out.println(Arrays.toString(arr));
        circularShiftLeft(arr);
        System.out.println(Arrays.toString(arr));
    }
}

Answer 7

我有这个作为面试问题。旋转 m 的一个简单的就地（并且有点直观） O(2n) 解决方案是获取数组，反转它，然后反转 [0, m] 和 (m, n] 子数组。我的解决方案，虽然有点不太明显，是原地的，并且 O(n) 基本上是在一个项目上将项目向前旋转一个，最终您将遍历所有元素，如果数组是距离的倍数，这就是 GCD 的位置。下面就做一个向右旋转，向左旋转留给读者作为练习：

public static void main(String[] args) {
    int[] f = {0, 4, 8, 2, 6, 7, 4, 5, 3};
    System.out.println(Arrays.toString(f));
    rotate(f, 3);
    System.out.println(Arrays.toString(f));
}

public static void rotate(int[] arr, int dist){
    int tmp, tmp2, gcd = GCD(arr.length, dist);
    for(int off=0;off<gcd;off++){
        tmp = arr[off];
        for(int i=0,idx=off;i<arr.length/gcd;idx=(idx+dist)%arr.length,i++){
            tmp2 = arr[(idx+dist)%arr.length];
            arr[(idx+dist)%arr.length] = tmp;
            tmp = tmp2;
        }
    }
}

public static int GCD(int a, int b) {
   if (b==0) return a;
   return GCD(b,a%b);
}