Как повернуть матрицу на 90 градусов против часовой стрелки в Java?

Question

Я пытаюсь разобраться с проблемами в книге «Взлом кодирования».Один из вопросов просит меня повернуть матрицу на 90 градусов по часовой стрелке.Теперь, пытаясь укрепить мое понимание вращения матрицы, я попытался встать перед новой проблемой: попытаться повернуть матрицу на 90 градусов против часовой стрелки (в другом направлении).

Я пытался пройти через слои квадратной матрицы, внешний слой, повторив весь путь до внутреннего слоя и поворачивая все индексы каждой стороны "квадрата" один за другим.Это в основном то, что реализовало решение Гейл Лакман Макдауэлл, но в другом направлении.

public static void rotateMatrix(int[][] matrix) {
        if(matrix.length == 0) {
            return;
        }
        for(int i = 0; i < matrix.length/2; i++) {
            int top = i;
            int bottom = matrix.length-1-i;
            for(int j = top; j < bottom; j++) {
                int temp = matrix[top][j];
                matrix[top][j] = matrix[j][matrix.length-1-j];
                matrix[j][matrix.length-1-j] = matrix[bottom][j];
                matrix[bottom][j] = matrix[j][matrix.length-1-bottom];
                matrix[j][matrix.length-1-bottom] = temp;
            }
        }
        }

Я ожидал, что результат выборки матрицы

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

будет

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

, но мой код привел к

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

.Где в моем коде ошибка / расхождение?

Answer 1

Если вы нарисуете матрицу для визуализации, вы увидите, что некоторые ваши индексы отключены. Например, вместо matrix.length-1, вы должны использовать bottom в ваших обновлениях, потому что размер квадрата слоя будет уменьшаться по мере увеличения i. Другая ошибка заключается в том, что во втором обновлении вы должны иметь:

matrix[j][bottom] = matrix[bottom][bottom - (j - top)];

вместо:

matrix[j][bottom] = matrix[bottom][j];

Это потому, что в нижнем ряду слоя индексы начинаются с последнего столбца и перемещаются назад к первому столбцу. j - top показывает, как далеко вы находитесь в верхнем ряду вашего слоя. После составления матрицы я обнаружил, что правильные обновления выглядят следующим образом:

public class matrix {
    public static void main(String[] args) {
        int n = 5;
        int[][] a = new int[n][n];
        for (int i = 0; i < n; i ++) {
            for (int j = 0; j < n; j ++) {
                a[i][j] = i * n + j + 1;
            }
        }
        rotateMatrix(a);
        for (int i = 0; i < a.length; i ++) {
            for (int j = 0; j < a[0].length; j ++) {
                System.out.printf("%3d", a[i][j]);
            }
            System.out.println();
        }
    }
    public static void rotateMatrix(int[][] matrix) {
        if (matrix.length == 0) {
            return;
        }
        for (int i = 0; i < matrix.length / 2; i++) {
            int top = i;
            int bottom = matrix.length - 1 - i;
            for (int j = top; j < bottom; j++) {
                int temp = matrix[top][j];
                matrix[top][j] = matrix[j][bottom];
                matrix[j][bottom] = matrix[bottom][bottom - (j - top)];
                matrix[bottom][bottom - (j - top)] = matrix[bottom - (j - top)][top];
                matrix[bottom - (j - top)][top] = temp;
            }
        }
    }
}

Выход:

  5 10 15 20 25
  4  9 14 19 24
  3  8 13 18 23
  2  7 12 17 22
  1  6 11 16 21

Answer 2

Вы работаете с одним экземпляром матрицы, устанавливаете значения в своей матрице, а также читаете старые значения, что, вероятно, вызывает вашу проблему.

Если функция вернет новую матрицу, это облегчит вашу работу.Ваш код может быть таким:

public static int[][] rotateMatrix(int[][] m) {
    if(m.length == 0) return new int[0][0];

    int rows = m.length, cols = m[0].length;
    int[][] result = new int[cols][rows];

    for(int row = 0; row < cols; row++) {
        for(int col = 0; col < rows; col++) {
            result[row][col] = m[col][rows - row - 1];
        }
    }

    return result;
}

Я бы также инкапсулировал массив int[][] в классе для обеспечения неизменности.