Java - 旋转数组

Java - Rotating array

提问by

So the goal is to rotate the elements in an array right atimes. As an example; if a==2, then array = {0,1,2,3,4}would become array = {3,4,0,1,2}

所以目标是正确旋转数组中的元素a。举个例子; 如果a==2, 那么 array = {0,1,2,3,4}将成为array = {3,4,0,1,2}

Here's what I have:

这是我所拥有的：

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

However, this fails to account for when [x+a]is greater than the length of the array. I read that I should store the ones that are greater in a different Array but seeing as ais variable I'm not sure that's the best solution. Thanks in advance.

但是，这无法说明何时[x+a]大于数组的长度。我读到我应该将较大的那些存储在不同的数组中，但看到a变量是我不确定这是最好的解决方案。提前致谢。

采纳答案by Sirko

Add a modulo array length to your code:

将模数组长度添加到您的代码中：

// 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];
}

You should also create a new Arrayto copy to, so you do not overwrite values, that you'll need later on.

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

回答by user2336315

In case you don't want to reinvent the wheel (maybe it's an exercise but it can be good to know), you can use Collections.rotate.

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

Be aware that it requires an array of objects, not primitive data type (otherwise you'll swap arrays themselves in the list).

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

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

回答by ponomandr

I think the fastest way would be using System.arrayCopy()which is native method:

我认为最快的方法是使用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);

It also reuses existing array. It may be beneficial in some cases. And the last benefit is the temporary array size is less than original array. So you can reduce memory usage when ais small.

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

回答by dusky

Another way is copying with System.arraycopy.

另一种方法是使用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);

回答by ThePatelGuy

Arraycopy is an expensive operation, both time and memory wise. Following would be an efficient way to rotate array without using extra space (unlike the accepted answer where a new array is created of the same size).

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--;
    }
}

回答by user3847870

Question : https://www.hackerrank.com/challenges/ctci-array-left-rotation
Solution : This is how I tried arrayLeftRotation method with complexity o(n)

问题：https
://www.hackerrank.com/challenges/ctci-array-left-rotation 解决方案：这就是我尝试复杂度为 o(n) 的 arrayLeftRotation 方法的方法

• looping once from k index to (length-1 )

• 2nd time for 0 to kth index

  public static int[] arrayLeftRotation(int[] a, int n, int k) {
  int[] resultArray = new int[n];
  int arrayIndex = 0;
  //first n-k indexes will be populated in this loop
  for(int i = k ; i resultArray[arrayIndex] = a[i];
  arrayIndex++;
  }
  // 2nd k indexes will be populated in this loop
  for(int j=arrayIndex ; j<(arrayIndex+k); j++){
  resultArray[j]=a[j-(n-k)];
  }
  return resultArray;
  }

• 从 k 索引到 (length-1) 循环一次

• 0 到第 k 个索引的第二次

  public static int[] arrayLeftRotation(int[] a, int n, int k) {
  int[] resultArray = new int[n];
  int arrayIndex = 0;
  // 将在此循环中填充第一个 nk 个索引
  for(int i = k ; i resultArray[arrayIndex] = a[i];
  arrayIndex++;
  }
  // 在此循环中将填充第二个 k 个索引
  for(int j=arrayIndex ; j<(arrayIndex+k); j++){
  resultArray[j]=a[j-(nk)];
  }
  return resultArray;
  }

回答by realPK

Java solution wrapped in a method:

封装在方法中的 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;
}

回答by manishkummar

For Left Rotate its very simple

对于左旋转它非常简单

Take the difference between length of the array and number of position to shift.

取数组长度和要移动的位置数之间的差值。

For Example

例如

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);

// print the output

// 打印输出

回答by Yuvaraj Ram

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] + " ");
        }
    }

}

回答by Arjun

In rubyrotating an array can be possible in one line.

在ruby中，可以在一行中旋转一个数组。

def array_rotate(arr)
   i, j = arr.length - 1, 0
   arr[j],arr[i], i, j = arr[i], arr[j], i - 1, j + 1 while(j<arr.length/2)
   puts "#{arr}"
end