Может ли этот алгоритм вращения матрицы O (n) быть выполнен на месте и остаться O (n)?

Question

Вопрос:

Может ли алгоритм, приведенный ниже, быть настроен на использование того же массива (который представляет 2D-матрицу) для вращения по часовой стрелке вместо использования второго массива и при этом оставаться на O (n) сложность?

Код:

import java.util.Random;

public class MatrixRotation {

  public static void main(String[] args) {
    int dimension = 5;

    int[] array = generate(dimension);
    print(array, dimension);

    int[] clockwise = clockwise(array, dimension);
    print(clockwise, dimension);
  }

  //Generate a matrix with random values
  private static int[] generate(int dimension) {
    Random rand = new Random();
    int[] array = new int[dimension * dimension];
    for(int i = 0; i < array.length; i++) {
      array[i] = rand.nextInt(10);
    }
    return array;
  }

  //Rotates the matrix clockwise by calculating where the value's position should be after the rotation
  private static int[] clockwise(int[] array, int dimension) {
    int[] rotated = new int[array.length];
    int baseCount = dimension;

    for(int i = 0; i < array.length; i++) {
      int remainder = i % dimension;

      if(remainder == 0)
        baseCount--;

      int position = baseCount + (dimension * remainder);

      //I suspect I can do some kinda swapping functionality here but am stumped

      rotated[position] = array[i];
    }

    return rotated;
  }

  //Used to display the matrix
  private static void print(int[] array, int dimension) {
    for(int i = 0; i < array.length; i++) {
      if(i % dimension == 0) 
        System.out.println();
      System.out.print(array[i] + " ");
    }
    System.out.println();
  }
}

Пример вывода:

1 7 4 1 4 
2 3 5 2 9 
4 3 9 3 1 
5 8 7 5 6 
3 3 7 2 5 

3 5 4 2 1 
3 8 3 3 7 
7 7 9 5 4 
2 5 3 2 1 
5 6 1 9 4 

Предыстория:

На днях я читал вопрос о поворотах матриц, представленных в одномерном массиве, и решил рассмотреть его. Мне удалось успешно создать алгоритм поворота, рассчитав следующую позицию значения после поворота. В настоящее время я пытаюсь определить, есть ли способ сохранить его как O (n), при этом уменьшая используемое пространство, сохраняя его в том же массиве. Есть мысли о том, как этого добиться?

Answer 1

Я нашел рабочее решение! Я не смог определить, как заставить его работать с опубликованным алгоритмом, но как только я начал проектировать его с нуля с чередованием вращения с самого начала, я нашел решение такой же сложности (по сути). Я разработал его с идеей работы снаружи внутрь через "луковые слои", находя углы каждого слоя, а затем вращая их и их смежные направления. Что-то вроде:

    ↓                      ↓                     ↓
    5 5 8 2 1 ←          7 5 8 2 5           7 2 8 2 5  
    9 4 8 2 3            9 4 8 2 3 ←         9 4 8 2 5 
    6 3 7 5 4            6 3 7 5 4         → 6 3 7 5 4 ←       Ect...
    2 6 4 2 7          → 2 6 4 2 7           5 6 4 2 7 
  → 7 0 7 5 5            5 0 7 5 1           5 0 7 3 1 
            ↑                  ↑                 ↑

Для каждого слоя.

Код:

  private static int[] clockwise2(int[] array, int dimension) {
    int layers = dimension / 2; //Total layers of the onion
    //Loop through the layers
    for (int i = 0; i < layers; i++) {
      int layerWidth = dimension - 2 * i; //Current layer width

      int topStart = i + dimension * i; //Top left corner
      int rightStart = topStart + (layerWidth - 1); //Top right corner
      int bottomStart = (array.length - 1) - topStart; //Bottom right corner
      int leftStart = bottomStart - (layerWidth - 1); //Bottom left corner

      //Loop values in current layer
      for (int j = 0; j < layerWidth - 1; j++) {
        int topIndex = topStart + j; //Move right
        int rightIndex = rightStart + dimension * j; //Move down
        int bottomIndex = bottomStart - j; //Move left
        int leftIndex = leftStart - dimension * j; //Move up

        //Swap the values in a circular direction
        int temp = array[topIndex];
        array[topIndex] = array[leftIndex];
        array[leftIndex] = array[bottomIndex];
        array[bottomIndex] = array[rightIndex];
        array[rightIndex] = temp;
      }
    }

    return array;
  }