Xoay ma trận vuông 90 độ ngược chiều kim đồng hồ trong Java

Cho ma trận vuông N×N. Nhiệm vụ là xoay ma trận 90 độ theo hướng ngược chiều kim đồng hồ (counterclockwise).

Ví dụ

Đầu vào (N=3):

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

Đầu ra:

3 6 9
2 5 8
1 4 7

Phương pháp: Chuyển vị + Đảo cột

Ý tưởng cốt lõi:

1. Tìm ma trận chuyển vị (transpose): hoán đổi hàng thành cột, cột thành hàng (matrix[i][j] ↔ matrix[j][i]).
2. Đảo thứ tự các hàng (hoặc cột tùy hướng xoay). Với xoay ngược chiều kim đồng hồ: đảo các cột theo chiều dọc (hoán đổi hàng đầu với hàng cuối).

Triển khai Java

public class RotateMatrix {
    public static void rotateCounterClockwise(int[][] matrix) {
        int n = matrix.length;
        // Bước 1: Chuyển vị (transpose)
        for (int i = 0; i < n; i++) {
            for (int j = i; j < n; j++) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[j][i];
                matrix[j][i] = temp;
            }
        }
        // Bước 2: Đảo các hàng theo chiều dọc (swap row top với bottom)
        for (int col = 0; col < n; col++) {
            int top = 0, bottom = n - 1;
            while (top < bottom) {
                int temp = matrix[top][col];
                matrix[top][col] = matrix[bottom][col];
                matrix[bottom][col] = temp;
                top++;
                bottom--;
            }
        }
    }

    public static void printMatrix(int[][] matrix) {
        for (int[] row : matrix) {
            for (int val : row) System.out.print(val + " ");
            System.out.println();
        }
    }

    public static void main(String[] args) {
        int[][] mat = {{1,2,3}, {4,5,6}, {7,8,9}};
        rotateCounterClockwise(mat);
        printMatrix(mat);
        // Kết quả:
        // 3 6 9
        // 2 5 8
        // 1 4 7
    }
}

Lưu ý

• Phương pháp này sửa đổi ma trận gốc (in-place), không cấp phát mảng mới.
• Độ phức tạp thời gian: O(N²), không gian: O(1).
• Nếu muốn xoay theo chiều kim đồng hồ: sau khi chuyển vị, hãy đảo các hàng theo chiều ngang (hoán đổi cột trái/phải).