Rotate Image

Q: Độ phức tạp thời gian và không gian của việc xoay ma trận là gì?

Việc xoay ma trận n × n mất thời gian O(n²), vì gần như mọi giá trị đều phải di chuyển một lần. Phương pháp chuyển vị rồi đảo ngược cần O(1) bộ nhớ bổ sung. Tạo một bản sao đã xoay cũng mất thời gian O(n²), nhưng dùng O(n²) bộ nhớ bổ sung.

Q: Bạn có thể xoay ma trận bằng cách di chuyển bốn giá trị mỗi lần không?

Có. Mỗi giá trị nằm ngoài tâm thuộc một chu kỳ gồm bốn ô: (i, j) , (j, n-1-i) , (n-1-i, n-1-j) và (n-1-j, i) . Xử lý từng vòng, giữ một giá trị trong mỗi chu kỳ vào một biến rồi dịch chuyển ba giá trị còn lại. Cách này có cùng độ phức tạp thời gian O(n²) và không gian O(1), nhưng có thêm phép tính chỉ số dễ viết sai.

Trung bìnhMảng và chuỗi Toán và mô phỏng

+10

Bạn được cho một lưới số nguyên n × n, mỗi hàng là một danh sách. Hãy xoay lưới một phần tư vòng theo chiều kim đồng hồ rồi trả về lưới đó. Hàng trên cùng trở thành cột ngoài cùng bên phải, hàng thứ hai trở thành cột bên trái cột đó, cứ thế tiếp tục: giá trị tại (i, j) chuyển đến (j, n-1-i). Bạn có thể thay đổi trực tiếp lưới; hãy trả về lưới đó.

Hàm

rotateImage(matrix: integer-2d-array) → integer-2d-array

matrixinteger-2d-array: lưới hình vuông, mỗi hàng có một danh sách bên trong
Trả vềinteger-2d-array: Ma trận đã xoay 90 độ theo chiều kim đồng hồ

Ràng buộc

n == matrix.length == matrix[i].length
1 ≤ n ≤ 70
-1000 ≤ matrix[i][j] ≤ 1000

Ví dụ

Đầu vào: matrix = [[3, 7, 1], [9, 5, 2], [4, 8, 6]]
Đầu ra: [[4, 9, 3], [8, 5, 7], [6, 2, 1]]
Giải thích: Hàng đầu tiên, 3 7 1, trở thành cột cuối cùng khi đọc từ trên xuống dưới. Cột đầu tiên, 3 9 4, khi đọc từ dưới lên trên, trở thành hàng đầu tiên [4, 9, 3]. Giá trị ở giữa 5 vẫn giữ nguyên vị trí.

Câu hỏi mở rộng

Bạn có thể thực hiện hai bước tại chỗ nào để xoay ma trận 180 độ, và có thể hoàn thành trong một lượt hoán đổi không?

Gợi ý

Mở từng gợi ý một. Mỗi gợi ý tiết lộ thêm một chút.

Đã mở 0/3

Lời giải

Vị trí mới của mỗi giá trị được xác định bằng công thức: (i, j) chuyển đến (j, n-1-i). Phần khó là di chuyển các giá trị mà không dùng ma trận thứ hai, vì khi ghi một giá trị vào ô mới, bạn sẽ ghi đè lên một giá trị chưa được di chuyển. Chuyển vị rồi đảo ngược thứ tự các hàng sẽ tạo ra cùng một phép xoay một phần tư bằng cách hoán đổi từng cặp.

Tạo bản sao đã xoay

Ý tưởng

Hàng i trở thành cột n-1-i, còn giá trị ở vị trí j trong hàng sẽ nằm ở vị trí j dọc theo cột đó, tức là hàng j. Vì vậy, result[j][n-1-i] = matrix[i][j]. Trong ví dụ đầu tiên, số 4 ở hàng 2, cột 0 chuyển đến hàng 0, cột 0, nên đáp án bắt đầu bằng số 4.

Các giá trị di chuyển theo chu kỳ gồm bốn vị trí, vì vậy nếu ghi trực tiếp vào ma trận ban đầu, bạn sẽ xóa mất một giá trị trước khi nó kịp di chuyển: số 3 sẽ ghi đè lên số 1 ở góc trên bên phải. Bản sao cần thêm n² ô, tức là 4,900 ô khi n = 70.

Thuật toán

Tạo một ma trận kết quả n × n.
Với mỗi hàng i và cột j, sao chép matrix[i][j] vào result[j][n-1-i].
Trả về kết quả.

def rotateImage(matrix):
    n = len(matrix)
    result = [[0] * n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            # Row i becomes column n-1-i, read from top to bottom.
            result[j][n - 1 - i] = matrix[i][j]
    return result

Chuyển vị, rồi đảo ngược từng hàng

Ý tưởng

Phép chuyển vị biến (i, j) thành (j, i), còn đảo ngược một hàng biến cột c thành cột n-1-c. Kết hợp hai thao tác này, (i, j) thành (j, n-1-i), đúng vị trí mà phép xoay đưa nó đến.

Cả hai thao tác đều thực hiện trực tiếp trên dữ liệu, vì mỗi thao tác gồm một loạt lần hoán đổi từng cặp. Khi chuyển vị, matrix[i][j] và matrix[j][i] đều nằm ở ô của nhau, nên chỉ cần một lần hoán đổi là xong. Chỉ hoán đổi các cặp có j > i, nếu không thì mọi cặp sẽ bị hoán đổi trở lại. Khi đảo ngược một hàng, ta hoán đổi hai đầu hàng rồi tiến dần vào giữa.

Ở ví dụ đầu tiên, phép chuyển vị tạo ra [[3, 9, 4], [7, 5, 8], [1, 2, 6]]: mỗi hàng lúc này chứa một cột trước đó. Đảo ngược từng hàng sẽ cho ra đáp án.

Phép chuyển vị thực hiện n(n-1)/2 lần hoán đổi, còn các phép đảo ngược thực hiện n·⌊n/2⌋ lần, nên độ phức tạp thời gian là O(n²), với một vài biến dùng thêm. Phiên bản R trước tiên sao chép đầu vào vào một ma trận R, nên bộ nhớ dùng thêm là O(n²).

Thuật toán

Với mỗi ô phía trên đường chéo chính, (i, j) với j > i, hãy đổi giá trị của ô đó với ô (j, i).
Với mỗi hàng, đổi chỗ giá trị đầu tiên và cuối cùng, rồi di chuyển hai đầu vào trong cho đến khi chúng gặp nhau.
Trả về ma trận.

def rotateImage(matrix):
    n = len(matrix)
    # Transpose: swap each value above the diagonal with its mirror below it.
    for i in range(n):
        for j in range(i + 1, n):
            matrix[i][j], matrix[j][i] = matrix[j][i], matrix[i][j]
    # Reverse each row with two pointers.
    for row in matrix:
        left, right = 0, n - 1
        while left < right:
            row[left], row[right] = row[right], row[left]
            left += 1
            right -= 1
    return matrix

Lỗi thường gặp và trường hợp biên

Chuyển vị với j bắt đầu từ 0. Mỗi cặp bị đổi chỗ hai lần, khiến các lần chuyển vị triệt tiêu lẫn nhau, nên kết quả chỉ là các hàng bị đảo ngược, tạo thành ảnh phản chiếu.
Đảo ngược trước khi chuyển vị. Thứ tự đó xoay ma trận ngược chiều kim đồng hồ. Một phép thử ma trận 2 × 2 sẽ phát hiện lỗi này: [[1, 2], [3, 4]] phải trở thành [[3, 1], [4, 2]].
Ghi matrix[j][n-1-i] = matrix[i][j] vào chính ma trận đó. Ô đích vẫn chứa một giá trị chưa được di chuyển, và giá trị đó sẽ bị mất.
Dùng n-i thay vì n-1-i. Với chỉ số bắt đầu từ 0, cột cuối cùng là n-1, nên n-i vượt quá giới hạn khi i = 0.

Câu hỏi thường gặp3

Độ phức tạp thời gian và không gian của việc xoay ma trận là gì?

Việc xoay ma trận n × n mất thời gian O(n²), vì gần như mọi giá trị đều phải di chuyển một lần. Phương pháp chuyển vị rồi đảo ngược cần O(1) bộ nhớ bổ sung. Tạo một bản sao đã xoay cũng mất thời gian O(n²), nhưng dùng O(n²) bộ nhớ bổ sung.

Làm thế nào để xoay một ma trận ngược chiều kim đồng hồ?

Đổi thứ tự của hai bước: đảo ngược từng hàng trước, rồi chuyển vị. Bạn cũng có thể chuyển vị trước, sau đó đảo ngược thứ tự các hàng. Dù làm theo cách nào, giá trị tại (i, j) cũng sẽ nằm ở (n-1-j, i).

Bạn có thể xoay ma trận bằng cách di chuyển bốn giá trị mỗi lần không?

Có. Mỗi giá trị nằm ngoài tâm thuộc một chu kỳ gồm bốn ô: (i, j), (j, n-1-i), (n-1-i, n-1-j) và (n-1-j, i). Xử lý từng vòng, giữ một giá trị trong mỗi chu kỳ vào một biến rồi dịch chuyển ba giá trị còn lại. Cách này có cùng độ phức tạp thời gian O(n²) và không gian O(1), nhưng có thêm phép tính chỉ số dễ viết sai.

def rotateImage(matrix):
    # Viết code ở đây

Kiểm thử #1

Kiểm thử #2

Đối số

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

Đầu ra mong đợi

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