Проблема

Повернуть массив из n элементов
вправо на k шагов.
Например, при n = 7 и k = 3
массив [1,2,3,4,5,6,7] вращается до [5,6,7,1,2 ,3,4].
Сколько различных способов
решения этой проблемы вы знаете?

Решение

//Intermediate array
//In a straightforward way, we can create 
//a new array and then copy elements to the new array. 
//Then change the original array by 
//using 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 );
}

Пространство равно O(n), а время равно O(n).

//Вращение пузыря
Можем ли мы сделать это за O(1)?

Это решение похоже на пузырьковую сортировку.

public static void rotate(int[] arr, int order) {
 if (arr == null || order < 0) {
     throw new IllegalArgumentException
  ("Illegal argument!");
 }
 
 for (int i = 0; i < order; i++) {
  for (int j = arr.length - 1; j > 0; j--) {
   int temp = arr[j];
   arr[j] = arr[j - 1];
   arr[j - 1] = temp;
  }
 }
}

Однако время равно O(n*k).

Вот пример (длина=7, порядок=3):
i=0
0 1 2 3 4 5 6
0 1 2 3 4 6 5
…
6 0 1 2 3 4 5
i=1
6 0 1 2 3 5 4
…
5 6 0 1 2 3 4
i=2
5 6 0 1 2 4 3
…
4 5 6 0 1 2 3

// Разворот

Можем ли мы сделать это за O(1) пространства и за O(n)
времени? Следующее решение делает.

Предположим, что нам дано {1,2,3,4,5,6}
и порядок 2. Основная идея такова:

  1. Разделить массив на две части: 1,2,3,4
    и 5, 6
    2. Повернуть первую часть: 4,3,2,1,5,6
    3. Повернуть вторую часть: 4,3,2,1,6,5
    4. Повернуть весь массив: 5,6,1,2,3,4
public static void rotate(int[] arr, int order) {
 order = order % arr.length;
 
 if (arr == null || order < 0) {
  throw new IllegalArgumentException
  ("Illegal argument!");
 }
 
 //length of first part
 int a = arr.length - order; 
 
 reverse(arr, 0, a-1);
 reverse(arr, a, arr.length-1);
 reverse(arr, 0, arr.length-1);
 
}
 
public static void reverse(int[] arr, 
int left, int right){
 if(arr == null || arr.length == 1) 
  return;
 
 while(left < right){
  int temp = arr[left];
  arr[left] = arr[right];
  arr[right] = temp;
  left++;
  right--;
 } 
}

Подробнее: http://www.programcreek.com/2015/03/rotate-array-in-java/