Java - 旋转阵列

Question

因此，我们的目标是旋转阵列中的元素a次。 作为一个例子;如果a==2，然后array = {0,1,2,3,4}将成为array = {3,4,0,1,2}

这是我有：

for (int x = 0; x <= array.length-1; x++){ 
    array[x+a] = array[x]; 
} 

然而，这无法说清时[x+a]比数组的长度。我读到，我应该存储在一个不同的阵列更大的，但看到作为a是变量，我不知道这是最好的解决方案。 在此先感谢。

Answer 1

添加一个模数组长度代码：

// create a newArray before of the same size as array 

// copy 
for(int x = 0; x <= array.length-1; x++){ 
    newArray[(x+a) % array.length ] = array[x]; 
} 

您还应该创建一个新的Array复制到，这样你就不会覆盖值，即你需要以后。

Answer 2

如果你不想重新发明轮子（也许这是一个练习，但它可以很好地知道），你可以使用Collections.rotate。

请注意，它需要一个对象数组，而不是原始数据类型（否则您将在列表中交换数组本身）。

Integer[] arr = {0,1,2,3,4}; 
Collections.rotate(Arrays.asList(arr), 2); 
System.out.println(Arrays.toString(arr)); //[3, 4, 0, 1, 2] 

Answer 3

我想以最快的方式将使用System.arrayCopy()这是本地方法：

int[] tmp = new int[a]; 
System.arraycopy(array, array.length - a, tmp, 0, a); 
System.arraycopy(array, 0, array, a, array.length - a); 
System.arraycopy(tmp, 0, array, 0, a); 

它还重用现有的阵列。在某些情况下这可能是有益的。 最后的好处是临时数组的大小比原始数组小。所以你可以减少内存使用a很小。

Answer 4

另一种方法是使用System.arraycopy复制。

int[] temp = new int[array.length]; 
    System.arraycopy(array, 0, temp, a, array.length - a); 
    System.arraycopy(array, array.length-a, temp, 0, a); 

Answer 5

Arraycopy是一个代价高昂的操作，无论是时间还是内存方面。 这将是一种有效的旋转数组的方法。

public void rotate(int[] nums, int k) { // k = 2 
    k %= nums.length; 
    // {0,1,2,3,4} 

    reverse(nums, 0, nums.length - 1); // Reverse the whole Array 
    // {4,3,2,1,0} 

    reverse(nums, 0, k - 1); // Reverse first part (4,3 -> 3,4) 
    // {3,4,2,1,0} 

    reverse(nums, k, nums.length - 1); //Reverse second part (2,1,0 -> 0,1,2) 
    // {3,4,0,1,2} 
} 

public void reverse(int[] nums, int start, int end) { 
    while (start < end) { 
     int temp = nums[start]; 
     nums[start] = nums[end]; 
     nums[end] = temp; 
     start++; 
     end--; 
    } 
} 

Answer 6

问题：https://www.hackerrank.com/challenges/ctci-array-left-rotation
解决方案： 这是我试图arrayLeftRotation方法与复杂性O（N）

• 从K指数循环一次（长度-1）

• 第二时间为0到第k个索引

  public static int [] arrayLeftRotation（int [] a，int n，int k）{
  int [] resultArray = new int [n];
  int arrayIndex = 0;
  //第一nk个索引将在该循环被填充
  对（INT I = K;我 resultArray [arrayIndex] = A [1];
  arrayIndex ++;
  }
  //第二ķ索引将是填充在该循环
  对（INT J = arrayIndex;Ĵ<（arrayIndex + K）; J ++）{
  resultArray [J] = A [J-（NK）];
  }
  返回resultArray;
  }

Answer 7

Java解决方案包裹在一个方法：

public static int[] rotate(final int[] array, final int rIndex) { 
    if (array == null || array.length <= 1) { 
     return new int[0]; 
    } 

    final int[] result = new int[array.length]; 
    final int arrayLength = array.length; 

    for (int i = 0; i < arrayLength; i++) { 
     int nIndex = (i + rIndex) % arrayLength; 
     result[nIndex] = array[i]; 
    } 
    return result; 
} 

Answer 8

用于向左旋转其非常简单

采取阵列的长度和数量的位置移位之间的差。

对于实例

int k = 2; 
int n = 5; 

int diff = n - k; 

int[] array = {1, 2, 3, 4, 5}; 
int[] result = new int[array.length]; 
System.arraycopy(array, 0, result, diff, k); 
System.arraycopy(array, k, result, 0, diff); 

//打印输出

Answer 9

package com.array.orderstatistics; 

import java.util.Scanner; 

public class ArrayRotation { 

    public static void main(String[] args) { 
     Scanner scan = new Scanner(System.in); 
     int n = scan.nextInt(); 
     int r = scan.nextInt(); 
     int[] a = new int[n]; 
     int[] b = new int[n]; 
     for (int i = 0; i < n; i++) { 
      a[i] = scan.nextInt(); 
     } 
     scan.close(); 

     if (r % n == 0) { 
      printOriginalArray(a); 
     } else { 
      r = r % n; 
      for (int i = 0; i < n; i++) { 
       b[i] = a[(i + r) < n ? (i + r) : ((i + r) - n)]; 
       System.out.print(b[i] + " "); 
      } 
     } 
    } 

    private static void printOriginalArray(int[] a) { 
     for (int i = 0; i < a.length; i++) { 
      System.out.print(a[i] + " "); 
     } 
    } 

}