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

我正在尝试使用仅一个1Darrays的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(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处缠绕自己，所以我们只需要等到我们到达那个位置。 我们可以certificate这个断言如下：假设我们遇到的第一个重复元素不是i 。 那么我们必须有两个不同的元素，当移位时会达到相同的位置 – 一个矛盾。

2. 假设我们完成了通过i, f(i), f(f(i)), ... ，但仍然存在未移位的元素（我们可以通过计算我们移动了多少元素来判断）。 我们现在如何找到包含这样一个元素的位置j ？ 而且，一旦我们完成了第二次迭代（通过j, f(j), f(f(j)), ... ）我们如何找到一个带有未移位元素的第三个位置？ 这也可能表明我们需要保存一个数组以考虑使用过的\ 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) 。 同样地，如果我们从S(i)得到一些y ，我们观察到一些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)的定义，我们可以取{0,...N - 1}任何d相邻元素组，并且它们中的每一个将被放置在不同的集合中。 这满足了第二个断言。

这意味着我们可以通过简单地将位置n mod N处的元素替换为位置0, d, 2d, ..., (N/d - 1)d元素来旋转位置0, d, 2d, ..., (N/d - 1)d的所有元素。位置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）中有O（1）空格
算法

• 将数组从0反转到n（numberOfPositions）位置
• 将数组从n + 1反转到数组长度 – 1个位置
• 将整个数组从0移动到长度 – 1个位置

  public class ArrayRotator { private final int[] target; private final int length; public ArrayRotator(int[] seed) { this.target = seed; this.length = seed.length; } public void rotateInline(int numberOfPositions) { reverse(0, numberOfPositions); reverse(numberOfPositions + 1, length-1); reverse(0, length-1); } private void reverse(int start, int end) { for (int i = start; i <= (start + end)/2; i++) { swap(i, start + end - i); } } private void swap(int first, int second) { int temp = this.target[second]; this.target[second] = this.target[first]; this.target[first] = temp; } } 

例如，假设数组为[1,2,3,4] ， n为2
在第一步之后，你最终会[2,1,3,4]
在第二步之后，你最终会[2,1,4,3]
在第三步之后，你最终会[3,4,1,2]

Answer 3

您可以通过迭代和复制来移动数据，这将是O（n）。 另一种方法是创建一个List实现，它包装您的数组并将其公开为循环移位。 这具有以下优点：当执行get或迭代时，实际移位是懒惰地完成的。

Answer 4

另一种方法是包装自己的结构，包括数组和虚拟零的索引。

Answer 5

我确实相信System.arraycopy实际上只会从一个数组中获取所有数据，并将其放入另一个刚刚移位的长度中。

无论如何，考虑这个问题是一项非常有趣的任务。 我现在能想到的唯一解决办法就是逐一解决问题。 不使用另一个数组，它看起来像这样：

 for(int i = 0; i < shift;i++) { tmp = array[0]; for(int j = 0;j 

对于大于30个项目的数组，使用它更有效：

 for (int i = 0; i < shift; i++) { tmp = array[0]; System.arraycopy( array, 1, array, 0, array.length - 1 ); array[array.length - 1] = tmp; } 

但是对于大arrays和接近数组大小以及短arrays和小移位的大移位，这种方法赢得了比赛：

  int[] array2 = new int[shift]; for (int i = 0; i < shift; i++) { array2[i] = array[i]; } System.arraycopy(array, shift, array, 0, array.length - shift); for (int i = array.length - shift; i < array.length; i++) { array[i] = array2[shift + i - array.length]; } 

我已经测试了一些数组大小和class次以下是结果

  int[] array = new int[100000]; int shift = 99999; 

以纳秒为单位：第一种方法：5663109208第二种方法：4047735536第三种方法：6085690所以你应该使用第三种方法。 希望有所帮助

Answer 6

我会一次将它移动1个元素，使用一个临时变量来保持元素，同时沿着每个元素移动元素1。 然后我会重复这两次以实现nclass次。

 public static void main( String[] args ) { int[] array = {1,2,3,4,5,6,7,8}; leftShift( array, 3); System.out.println( Arrays.toString( array)); } public static void leftShift(int[] array, int n) { for (int shift = 0; shift < n; shift++) { int first = array[0]; System.arraycopy( array, 1, array, 0, array.length - 1 ); array[array.length - 1] = first; } } 

输出：

 [4, 5, 6, 7, 8, 1, 2, 3] 

效率不高，因为System.arraycopy()已经过高度优化。

Answer 7

 for (int i = 0; i < n; i++) array[array.length - n + i] = array[i]; for (int i = 0; i < array.length - n; i++) array[i] = array[i + n]; 

Answer 8

查看此github链接：

https://github.com/techpanja/interviewproblems/blob/master/src/arrays/circularshiftintarray/CircularShiftArray.java

circularShiftToLeftInPlace

Answer 9

也许是一个旧post..但是在这里你是我的解决方案（其中A显然是数组， K是位置数）。

 public int[] solution(int[] A, int K){ int[] result = new int[A.length]; for (int i = 0; i 

Answer 10

Java 8版本：

 public class Sample { public static void main(String[] args) { int[] answer = solution(new int[] {1,2,3,4}, 2); Arrays.stream(answer).forEach(System.out::print); } public static int[] solution(int[] A, int K) { List numbers = IntStream.of(A).boxed().collect(Collectors.toList()); Collections.rotate(numbers, K); return numbers.stream().mapToInt(n -> n).toArray(); } } 

Answer 11

这个怎么样？

  // Left shift the array in O(n) with O(1) space. public static void leftShift(int[] array, int n) { int temp; int len = array.length; for (int i = 0; i < n; i++) { temp = array[len - n + i]; array[len - n + i] = array[i]; array[i] = array[n + i]; array[n + i] = temp; } }