java 如何旋转数组？

How to rotate an array?

提问by Linux Le

I have the following problem to test:

我有以下问题要测试：

Rotate an array of n elements to the right by k steps.

For instance, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4]. How many different ways do you know to solve this problem?

将包含 n 个元素的数组向右旋转 k 步。

例如，当 n = 7 且 k = 3 时，数组 [1,2,3,4,5,6,7] 被旋转到 [5,6,7,1,2,3,4]。你知道多少种不同的方法来解决这个问题？

My solution in intermediate array:

我在中间数组中的解决方案：

With Space is O(n)and time is O(n), I can create a new array and then copy elements to the new array. Then change the original array by using System.arraycopy().

使用 Space isO(n)和 time is O(n)，我可以创建一个新数组，然后将元素复制到新数组中。然后使用 更改原始数组System.arraycopy()。

public void rotate(int[] nums, int k) {
    if(k > nums.length) 
        k=k%nums.length;

    int[] result = new int[nums.length];

    for(int i=0; i < k; i++){
        result[i] = nums[nums.length-k+i];
    }

    int j=0;
    for(int i=k; i<nums.length; i++){
        result[i] = nums[j];
        j++;
    }

    System.arraycopy( result, 0, nums, 0, nums.length );
}

But is there a better way we can do it with bubble rotate(like bubble sort) in O(1) space?

但是有没有更好的方法可以用O(1) 空间中的气泡旋转（如气泡排序）来做到这一点？

回答by Diversity

You don't need the for- loops.

你不需要for- 循环。

public int[] rotate(int[] nums, int k) {
     if(k > nums.length) 
          k=k%nums.length;

     int[] result = new int[nums.length];
     System.arraycopy( nums, k+1, result, 0, k );
     System.arraycopy( nums, 0, result, k+1, nums.length-1 );

     //Case 1: The rotated array will be assigned to the given array "nums"
     nums = result;

     return result; //Case 2: method returns the rotated array
}

Specification of arraycopy can be found here http://docs.oracle.com/javase/7/docs/api/java/lang/System.html

可以在此处找到 arraycopy 的规范http://docs.oracle.com/javase/7/docs/api/java/lang/System.html

Not testet. The overall complexity of method rotate O(1).

不是睾丸。方法旋转的整体复杂度为 O(1)。

If your question was about all possible permutation have a look here Java Code for permutations of a list of numbers

如果您的问题是关于所有可能的排列，请查看此处的 Java 代码以获取数字列表的排列

Another advise is to check out the Java Collection APIwhich provides many sophisticated data structures and common sort algorithms, which are all implemented in a very efficient way.

另一个建议是查看Java Collection API，它提供了许多复杂的数据结构和常见的排序算法，它们都以非常有效的方式实现。

EDIT due to comment.

由于评论而编辑。

The method returns a rotated array. You can use the method within an outer method like this: (Just pseudo-code)

该方法返回一个旋转的数组。您可以在这样的外部方法中使用该方法：（只是伪代码）

void rotator(int[] nums) {        
       int rotated[] = nums;
       //Can be invoked iteraritve or within a loop like this
       rotated = rotate(rotated, 3);          
}

回答by TryinHard

Method 1 - The Reversal Algorithm(Good One):

方法 1 -反转算法（好一个）：

Algorithm:

rotate(arr[], d, n)

reverse(arr[], l, n);

reverse(arr[], 1, n-d) ;

reverse(arr[], n - d + 1, n);

算法：

旋转（arr []，d，n）

反向（arr[]，l，n）；

反向(arr[], 1, nd) ;

反向（arr[]，n - d + 1，n）；

Let AB are the two parts of the input array where A = arr[0..n-d-1] and B = arr[n-d..n-1]. The idea of the algorithm is:

让 AB 是输入数组的两部分，其中 A = arr[0..nd-1] 和 B = arr[nd..n-1]。该算法的思想是：

Reverse all to get (AB) r = BrAr.

Reverse A to get BrA. /* Ar is reverse of A */

Reverse B to get BA. /* Br is reverse of B */

反转所有得到 (AB) r = BrAr。

反转A得到BrA。/* Ar 是 A 的反向 */

反转 B 获得 BA。/* Br 是 B 的反向 */

For arr[] = [1, 2, 3, 4, 5, 6, 7], d =2 and n = 7

对于 arr[] = [1, 2, 3, 4, 5, 6, 7], d =2 和 n = 7

A = [1, 2, 3, 4, 5] and B = [ 6, 7]

A = [1, 2, 3, 4, 5] 和 B = [ 6, 7]

Reverse all, we get BrAr = [7, 6, 5, 4, 3, 2, 1]

Reverse A, we get ArB = [7, 6, 1, 2, 3, 4, 5] Reverse B, we get ArBr = [6, 7, 5, 4, 3, 1, 2]

反过来，我们得到 BrAr = [7, 6, 5, 4, 3, 2, 1]

反向 A，我们得到 ArB = [7, 6, 1, 2, 3, 4, 5] 反向 B，我们得到 ArBr = [6, 7, 5, 4, 3, 1, 2]

Here is the Code Snippet:

这是代码片段：

void righttRotate(int arr[], int d, int n)
{
  reverseArray(arr, 0, n-1);
  reverseArray(arr, 0, n-d-1);
  reverseArray(arr, n-d, n-1);
}

void reverseArray(int arr[], int start, int end)
{
  int i;
  int temp;
  while(start < end)
  {
    temp = arr[start];
    arr[start] = arr[end];
    arr[end] = temp;
    start++;
    end--;
   }
}

Method 2 - A Juggling Algorithm

方法 2 -杂耍算法

Divide the array in different sets where number of sets is equal to GCD of n and d and move the elements within sets.

将数组划分为不同的集合，其中集合的数量等于 n 和 d 的 GCD，并在集合内移动元素。

If GCD is 1, then elements will be moved within one set only, we just start with temp = arr[0] and keep moving arr[I+d] to arr[I] and finally store temp at the right place.

如果 GCD 为 1，则元素将仅在一组内移动，我们只需从 temp = arr[0] 开始，并不断将 arr[I+d] 移动到 arr[I]，最后将 temp 存储在正确的位置。

Here is an example for n =12 and d = 3. GCD is 3 and

这是 n = 12 和 d = 3 的示例。 GCD 是 3 并且

Let arr[] be {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

令 arr[] 为 {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12}

1. Elements are first moved in first set arr[] after this step --> {4 2 3 7 5 6 10 8 9 1 11 12}

2. Then in second set. arr[] after this step --> {4 5 3 7 8 6 10 11 9 1 2 12}

3. Finally in third set. arr[] after this step --> {4 5 6 7 8 9 10 11 12 1 2 3}

1. 在这一步之后，元素首先在第一个集合 arr[] 中移动 --> {4 2 3 7 5 6 10 8 9 1 11 12}

2. 然后在第二组。arr[] 在这一步之后 --> {4 5 3 7 8 6 10 11 9 1 2 12}

3. 终于到了第三盘。arr[] 在这一步之后 --> {4 5 6 7 8 9 10 11 12 1 2 3}

Here is the code:

这是代码：

void leftRotate(int arr[], int d, int n)
{
  int i, j, k, temp;
  int gcd = gcd(d, n);
  for (i = 0; i < gcd; i++)
  {
    /* move i-th values of blocks */
    temp = arr[i];
    j = i;
    while(1)
    {
      k = j + d;
      if (k >= n)
        k = k - n;
      if (k == i)
        break;
      arr[j] = arr[k];
      j = k;
    }
    arr[j] = temp;
  }
}

int gcd(int a,int b)
{
   if(b==0)
     return a;
   else
     return gcd(b, a%b);
}

Time complexity: O(n)

Auxiliary Space: O(1)

时间复杂度：O(n)

辅助空间：O(1)

Method 3 - Rotate one by one:

方法 3 -一一旋转：

righttRotate(arr[], d, n)

start

For i = 0 to i < d

Right rotate all elements of arr[] by one

end

righttRotate(arr[], d, n)

开始

对于 i = 0 到 i < d

将 arr[] 的所有元素右旋转一

结尾

To rotate by one, store arr[n-1] in a temporary variable temp, move arr[1] to arr[2], arr[2] to arr[3] …and finally temp to arr[0]

要旋转一，将 arr[n-1] 存储在临时变量 temp 中，将 arr[1] 移动到 arr[2]，将 arr[2] 移动到 arr[3] ...最后将 temp 移动到 arr[0]

Let us take the same example arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2, rotate arr[] by one 2 times. We get [7, 1, 2, 3, 4, 5, 6] after first rotation and [ 6, 7, 1, 2, 3, 4, 5] after second rotation.

让我们以同样的例子 arr[] = [1, 2, 3, 4, 5, 6, 7], d = 2，将 arr[] 旋转 1 次 2 次。我们在第一次旋转后得到 [7, 1, 2, 3, 4, 5, 6] ，在第二次旋转后得到 [ 6, 7, 1, 2, 3, 4, 5] 。

Her is Code Snippet:

她是代码片段：

void leftRotate(int arr[], int d, int n)
{
  int i;
  for (i = 0; i < d; i++)
    leftRotatebyOne(arr, n);
}

void leftRotatebyOne(int arr[], int n)
{
  int i, temp;
  temp = arr[n-n];
  for (i = 0; i < n-1; i++)
     arr[i] = arr[i+1];
  arr[n - 1] = temp;
}

Time complexity: O(n*d)

Auxiliary Space: O(1)

时间复杂度：O(n*d)

辅助空间：O(1)

回答by Md Johirul Islam

The following code will do your job. This is for right rotate.

以下代码将完成您的工作。这是用于右旋。

public void rightrotate(int[] nums, int k) {
    k %= nums.length;
    reverse(nums, 0, nums.length - 1);
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
}

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

If you want to do left rotate just use the following

如果你想做左旋转只需使用以下

 public void leftrotate(int[] nums, int k) {
    k %= nums.length;
    reverse(nums, 0, k - 1);
    reverse(nums, k, nums.length - 1);
    reverse(nums, 0, nums.length - 1);
}

回答by saka1029

Space is O(1) and time is O(n)

空间是 O(1) 时间是 O(n)

static void rotate(int[] array, int k) {
    int size = array.length;
    if (size <= 1) return;
    k = k % size;
    if (k == 0) return;
    for (int i = 0, start = 0, from = 0, to = -1, move = array[0]; i < size; ++i, from = to) {
        to = (from + k) % size;
        int temp = array[to];
        array[to] = move;
        move = to == start ? array[to = ++start] : temp;
    }
}

回答by nurawat

Partial Code for ONE time array rotation

一次性数组旋转的部分代码

       last=number_holder[n-1];
       first=number_holder[0];
        //rotation 

        number_holder[0]=last;

        for(i=1;i<n;i++)
        {
            last=number_holder[i];
            number_holder[i]=first;
            first=last;
        }

Display the array

显示数组

        for(i=1;i<n;i++)
        {
          System.out.println(number_holder[i]);
        }

回答by Harshit

ArrayUtil class is used to provide following utilities in primitive array

ArrayUtil 类用于在原始数组中提供以下实用程序

1. swap array elements
2. reverse array between startIndex and endIndex
3. leftRotate array by shift

1. 交换数组元素
2. startIndex 和 endIndex 之间的反向数组
3. 按移位左旋转数组

---

---

Algorithm for array rotation by shift-

通过移位进行阵列旋转的算法-

1. If we have to reverse array by shift value then take mod(%) with array length so that shift will become smaller than array length.
2. Reverse array between index 0 and shift-1
3. Reverse array between index shift and length-1.
4. Reverse complete array between index 0 and length-1.

1. 如果我们必须按移位值反转数组，则使用数组长度取 mod(%)，这样移位将变得小于数组长度。
2. 在索引 0 和 shift-1 之间反转数组
3. 在索引移位和长度 1 之间反转数组。
4. 反转索引 0 和长度 1 之间的完整数组。

Space Complexity:In-place Algorithm, No extra space needed so O(1).

空间复杂度：就地算法，不需要额外的空间，所以 O(1)。

Time Complexity :Array reversal of size k take O(k/2) i.e swapping k/2 pairs of elements.

时间复杂度：大小为 k 的数组反转需要 O(k/2)，即交换 k/2 对元素。

Array Reversal time- O(k) for k size array.

数组反转时间 - 对于 k 大小的数组，O(k)。

Total time in Rotation-

旋转总时间-

• O(1) ..........for step 1
• O(shift) ......for step 2
• O(n - shift) ...for step 3
• O(n) ...........for step 4

• O(1) ..... 用于第 1 步
• O(shift) ......用于第 2 步
• O(n - shift) ...对于第 3 步
• O(n) ........... 用于第 4 步

Total Time for array Rotation: O(1) + O(shift) + O(n-shift) + O(n) = O(n)

阵列旋转的总时间：O(1) + O(shift) + O(n-shift) + O(n) = O(n)

public class Solution {

    public static void main(String[] args) {
        int k = 3;
        int a[] = {1,2,3,4,5,6,7};

        ArrayUtil.leftRotate(a, k);

        for (int i : a)
            System.out.println(i);
    }
}

class ArrayUtil {

    public static final boolean checkIndexOutOfRange(int[] array, int index) {
        if (index < 0 || index > array.length)
            return true;
        return false;
    }

    public static final void swap(int[] array, int i, int j) {
        if (checkIndexOutOfRange(array, i) || checkIndexOutOfRange(array, j))
            return;
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }

    public static final void reverse(int[] array, int startIndex, int endIndex) {
        if (checkIndexOutOfRange(array, startIndex) || checkIndexOutOfRange(array, endIndex))
            return;
        while (startIndex < endIndex) {
            swap(array, startIndex, endIndex);
            startIndex++;
            endIndex--;
        }
    }

    public static final void reverse(int[] array) {
        reverse(array, 0, array.length - 1);
    }

    public static final void leftRotate(int[] array, int shift) {
        int arrayLength = array.length;
        if (shift >= arrayLength)
            shift %= arrayLength;
        reverse(array, 0, shift - 1);
        reverse(array, shift, arrayLength - 1);
        reverse(array);
    }
}

回答by Rohit Mourya

Above solutions talk about shifting array elements either by reversing them or any other alternative.

上述解决方案讨论了通过反转数组元素或任何其他替代方法来移动数组元素。

I've unique solution. How about determining the starting position of element after n rotations. Once we know that, then simply insert elements from that index and increment counter using modulus operation. Using this method we can avoid using extra array operations and so on.

我有独特的解决方案。如何确定 n 次旋转后元素的起始位置。一旦我们知道了这一点，那么只需从该索引插入元素并使用模数运算递增计数器。使用这种方法我们可以避免使用额外的数组操作等。

Here is my code:

这是我的代码：

#include <cmath>
#include <cstdio>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;

void rotateLeft(int n,int r) {
    vector<long int> vec(n);
    int j = n;
    // get the position of starting index after r left rotations.
    while(r!=0) {
        --j;
        if(j==0)
            j = n;
        --r;
    }
    for(long int i=0;i<n;++i) {
        // simply read the input from there and increment j using modulus operator.
        cin>>vec[j];
        j = (j+1)%n;
    }
    // print the array
    for(long int i=0;i<n;++i) 
        cout<<vec[i]<<" ";
}
int rotateRight (int n,int r) {
    // get the position of starting index after r left rotations.
    int j = r % n;

    vector<long int> vec(n);
    for(int i=0;i<n;i++) {
        cin>>vec[j];
        j=(j+1)%n;
    }
    for(int i=0;i<n;i++)
        cout<<vec[i]<<" ";

}
int main() {

    long int n,r;   // n stands from number of elements in array and r stands for rotations.
    cin>>n>>r;
    // Time Complexity: O(n+r) Space Complexity: O(1)
    rotateLeft(n,r);
    // Time Complexity: O(n) Space Complexity: O(1)
    rotateRight(n,r);
    return 0;

}

回答by Girish Gupta

Python code:

蟒蛇代码：

def reverse(arr,start , end):   
    while(start <= end):
        arr[start] , arr[end] = arr[end] , arr[start]
        start = start+1
        end = end-1

arr = [1,2,3,4,5,6,7]
n = 7
k = 2
reverse(arr,0,n-1)
# [7,6,5,4,3,2,1]
reverse(arr,0,n-1-k)
# [3,4,5,6,7,2,1]
reverse(arr,n-k,n-1)
# [3,4,5,6,7,1,2]

print arr
# [3, 4, 5, 6, 7, 8, 9, 1, 2]

回答by Arjun

In Ruby Its very simple, Please take a look, Its 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

Input: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

输入：[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]

Output: [20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

输出：[20, 19, 18, 17, 16, 15, 14, 13, 12, 11, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1]

回答by Neelam Chahal

1.using a temp array and O(n) time

1.使用临时数组和 O(n) 时间

public static void rotateAnArrayUsingTemp(int arr[], int d, int n) {
    int temp[] = new int[d];
    int tempIndex = 0;
    for (int i = 0; i < d; i++) {
        temp[i] = arr[i];
    }
    for (int i = 0; i < arr.length - d; i++) {
        arr[i] = arr[i + d];
    }
    for (int i = arr.length - d; i < arr.length; i++) {
        arr[i] = temp[tempIndex++];
    }
}