Transpose Matrix

Q: Độ phức tạp thời gian của việc chuyển vị một ma trận là bao nhiêu?

O(m × n) : mỗi giá trị trong m × n được sao chép một lần, và không thể tạo ra kết quả bằng ít thao tác hơn. Ma trận mới cần O(m × n) bộ nhớ, bằng kích thước của chính đầu ra.

Q: Bạn có thể chuyển vị một ma trận ngay tại chỗ không?

Với ma trận vuông thì có thể: đổi chỗ matrix[i][j] với matrix[j][i] cho mọi ô phía trên đường chéo, chỉ cần thêm O(1) bộ nhớ. Ma trận không vuông sẽ đổi hình dạng, nên nếu dùng danh sách các hàng, bạn cần một ma trận mới.

Người mớiMảng và chuỗi

+10

Bạn nhận được một ma trận số nguyên dưới dạng danh sách các hàng: matrix[i][j] là giá trị ở hàng i, cột j. Hãy trả về ma trận chuyển vị của nó: giá trị ở hàng i, cột j chuyển đến hàng j, cột i, vì vậy mỗi hàng trở thành một cột. Ma trận không nhất thiết phải là ma trận vuông: ma trận m × n trở thành ma trận n × m.

Hàm

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

matrixinteger-2d-array: ma trận m × n, dưới dạng danh sách gồm m hàng, mỗi hàng có n số nguyên
Trả vềinteger-2d-array: ma trận chuyển vị n × m, dưới dạng danh sách gồm n hàng, mỗi hàng có m số nguyên

Ràng buộc

1 ≤ m, n ≤ 1000, trong đó m = matrix.length và n = matrix[i].length
m × n ≤ 5000
Mỗi hàng có cùng độ dài n.
-1000 ≤ matrix[i][j] ≤ 1000

Ví dụ

Đầu vào: matrix = [[1, 2, 3], [4, 5, 6]]
Đầu ra: [[1, 4], [2, 5], [3, 6]]
Giải thích: Hàng [1, 2, 3] trở thành cột đầu tiên và [4, 5, 6] trở thành cột thứ hai. Đọc theo từng hàng, ta có kết quả [1, 4], [2, 5], [3, 6]: một ma trận 3 × 2.

Câu hỏi mở rộng

Giả sử ma trận được lưu dưới dạng một mảng phẳng gồm m × n giá trị, theo từng hàng. Bạn có thể chuyển vị một ma trận không vuông ngay trong mảng đó mà không cần mảng thứ hai 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

Phép chuyển vị không tính toán gì cả: giá trị tại (i, j) chuyển đến (j, i). Công việc nằm ở hình dạng. Kết quả có n hàng, mỗi hàng dài m, vì vậy không thể chuyển vị tại chỗ một danh sách các hàng không vuông; hãy tạo ma trận mới có kích thước đảo lại rồi điền dữ liệu vào.

Đọc ma trận theo từng cột một

Ý tưởng

Hàng j của kết quả là cột j của đầu vào, đọc từ trên xuống dưới. Với [[1, 2, 3], [4, 5, 6]], cột 0 lần lượt có 1 rồi 4, nên hàng đầu tiên của kết quả là [1, 4].

Mỗi giá trị được đọc một lần và ghi một lần: thời gian O(m × n) và bộ nhớ O(m × n) cho kết quả. Khi tạo mỗi hàng mới, ta lần lượt nhảy qua từng hàng của đầu vào thay vì đọc dọc theo một hàng, đây là cách truy cập bộ nhớ chậm hơn.

Thuật toán

Gọi m là số hàng và n là độ dài của một hàng.
Với mỗi cột j từ 0 đến n-1, hãy bắt đầu bằng một danh sách rỗng.
Thêm matrix[i][j] vào danh sách đó với mọi i từ 0 đến m-1.
Thêm danh sách đó vào kết quả dưới dạng hàng j, rồi trả về kết quả sau cột cuối cùng.

def transpose(matrix):
    m, n = len(matrix), len(matrix[0])
    result = []
    for j in range(n):
        # Column j, read top to bottom, becomes row j of the answer.
        column = []
        for i in range(m):
            column.append(matrix[i][j])
        result.append(column)
    return result

Điền vào một lưới n × m mới bằng cách phản chiếu từng ô

Ý tưởng

Tạo trước kết quả n × m, sau đó đọc dữ liệu đầu vào theo thứ tự lưu trữ, từng hàng một, rồi đặt mỗi giá trị vào vị trí đối xứng: result[j][i] = matrix[i][j]. Cách này chính xác vì phép chuyển vị chính là thao tác đổi chỗ các chỉ số này, áp dụng một lần cho mỗi ô.

Mỗi giá trị chỉ được sao chép một lần, nên thời gian là O(m × n), còn lưới chiếm O(m × n) bộ nhớ mà đầu ra vốn cần. Đọc lần lượt theo các hàng sẽ truy cập bộ nhớ theo thứ tự lưu trữ, và mỗi hàng của kết quả chỉ được cấp phát một lần với kích thước cuối cùng.

Thuật toán

Gọi m là số hàng và n là độ dài của một hàng.
Tạo result gồm n hàng, mỗi hàng chứa m giá trị.
Với mỗi hàng i và mỗi cột j của đầu vào, đặt result[j][i] = matrix[i][j].
Trả về result.

def transpose(matrix):
    m, n = len(matrix), len(matrix[0])
    # The answer has n rows of m values each.
    result = [[0] * m for _ in range(n)]
    for i in range(m):
        for j in range(n):
            result[j][i] = matrix[i][j]
    return result

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

Tạo kết quả có hình dạng giống đầu vào. Với ví dụ 2 × 3, viết result[2][0] sẽ vượt quá chỉ số cuối: kết quả cần có n hàng, mỗi hàng dài m.
Hoán đổi matrix[i][j] với matrix[j][i] ngay tại chỗ. Cách này chỉ hiệu quả khi m = n, và chỉ với các ô có j > i; vòng lặp qua mọi ô sẽ hoán đổi mỗi cặp hai lần và trả về ma trận không đổi.
Trong Python, [[0] * m] * n tạo ra n tham chiếu đến cùng một danh sách, nên khi ghi vào một ô, cả một cột sẽ thay đổi. Hãy tạo riêng từng hàng.
Trong C, hàm gọi đọc *returnSize là số hàng của kết quả, n, và (*returnColumnSizes)[j] là độ dài của từng hàng, m.

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

Ma trận chuyển vị là gì?

Đó là ma trận (matrix) bạn nhận được khi đổi hàng thành cột và cột thành hàng: giá trị ở hàng i, cột j chuyển đến hàng j, cột i. Ma trận 2 × 3 trở thành ma trận 3 × 2, và chuyển vị hai lần sẽ đưa ma trận về trạng thái ban đầu.

Độ phức tạp thời gian của việc chuyển vị một ma trận là bao nhiêu?

O(m × n): mỗi giá trị trong m × n được sao chép một lần, và không thể tạo ra kết quả bằng ít thao tác hơn. Ma trận mới cần O(m × n) bộ nhớ, bằng kích thước của chính đầu ra.

Bạn có thể chuyển vị một ma trận ngay tại chỗ không?

Với ma trận vuông thì có thể: đổi chỗ matrix[i][j] với matrix[j][i] cho mọi ô phía trên đường chéo, chỉ cần thêm O(1) bộ nhớ. Ma trận không vuông sẽ đổi hình dạng, nên nếu dùng danh sách các hàng, bạn cần một ma trận mới.

def transpose(matrix):
    # Viết code tại đây

Kiểm thử #1

Kiểm thử #2

Đối số

matrix = [[1, 2, 3], [4, 5, 6]]

Đầu ra mong đợi

[[1, 4], [2, 5], [3, 6]]