Set Matrix Zeroes

Q: Độ phức tạp thời gian của bài toán Đặt các phần tử trong ma trận thành 0 là bao nhiêu?

O(m·n) cho ma trận m × n , vì mỗi ô được đọc và ghi một số lần cố định. Không có lời giải nào hiệu quả hơn, vì bất kỳ ô nào bị bỏ qua cũng có thể là số 0 làm thay đổi kết quả. Bộ nhớ phụ là O(m + n) khi dùng các mảng đánh dấu và O(1) khi dùng hàng đầu tiên và cột đầu tiên làm dấu.

Trung bìnhMảng và chuỗi Băm

+10

Đầu vào là một lưới m × n gồm các số nguyên, được cho theo từng hàng, vì vậy matrix[i][j] nằm ở hàng i và cột j. Ở vị trí nào có số 0 trong lưới, hãy đặt toàn bộ hàng và toàn bộ cột tương ứng thành 0. Chỉ tính các số 0 có sẵn từ đầu: ô bạn đổi thành 0 sẽ không làm hàng hoặc cột của nó bị đổi thành 0. Bạn có thể thay đổi trực tiếp lưới, hãy trả về lưới đó.

Hàm

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

matrixinteger-2d-array: lưới số nguyên, mỗi hàng là một danh sách bên trong
Trả vềinteger-2d-array: ma trận có mọi hàng và mọi cột từng chứa số 0 đều được đặt thành 0

Ràng buộc

m == matrix.length và n == matrix[i].length
1 ≤ m, n ≤ 1000 và m × n ≤ 5000
Tất cả các hàng m chứa n giá trị.
-1000 ≤ matrix[i][j] ≤ 1000

Ví dụ

Đầu vào: matrix = [[3, 8, 1], [5, 0, 7], [2, 6, 4]]
Đầu ra: [[3, 0, 1], [0, 0, 0], [2, 0, 4]]
Giải thích: Số 0 duy nhất nằm ở hàng 1, cột 1. Hàng 1 trở thành toàn số 0, cột 1 cũng vậy, khiến số 8 và số 6 chuyển thành 0. Bốn góc không nằm trên cả hai đường này nên giữ nguyên giá trị.

Câu hỏi mở rộng

Cách tiếp cận tốt nhất bên dưới dùng thêm hai giá trị boolean. Bạn có thể dùng một giá trị, để matrix[0][0] đại diện cho hàng đầu tiên không?

Lời giải

Số 0 bạn ghi ra trông giống hệt số 0 có sẵn, nên việc xóa các hàng trong lúc quét sẽ làm số 0 lan ra khắp ma trận. Hãy tách riêng việc đọc và ghi: trước tiên ghi lại những hàng và cột có số 0, sau đó xóa chúng. Lưu thông tin đó trong hai mảng, hoặc để dùng thêm O(1) không gian, lưu ngay trong hàng đầu tiên và cột đầu tiên của ma trận.

Đánh dấu hàng và cột trong hai mảng

Ý tưởng

Một ô có giá trị 0 đúng khi hàng hoặc cột của nó chứa giá trị 0 lúc bắt đầu. Vì vậy, hãy ghi lại hai danh sách thông tin, zeroRow[i] và zeroCol[j], trong một lượt duyệt không ghi dữ liệu, sau đó xóa mọi ô có hàng hoặc cột được đánh dấu. Không có giá trị nào lan ra, vì mọi thao tác đọc đều diễn ra trước lần ghi đầu tiên.

Mỗi lượt duyệt thăm m·n ô đúng một lần, nên thời gian chạy là O(m·n), còn các mảng chứa m + n giá trị boolean.

Thuật toán

Tạo zeroRow có m phần tử và zeroCol có n phần tử, tất cả đều là false.
Duyệt qua từng ô. Khi matrix[i][j] bằng 0, đặt zeroRow[i] và zeroCol[j] thành true.
Duyệt lại từng ô và đặt ô đó thành 0 nếu zeroRow[i] hoặc zeroCol[j] là true.
Trả về ma trận.

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    zero_row = [False] * m
    zero_col = [False] * n
    # Pass 1: only read, so a new zero can never spread further.
    for i in range(m):
        for j in range(n):
            if matrix[i][j] == 0:
                zero_row[i] = True
                zero_col[j] = True
    # Pass 2: write.
    for i in range(m):
        for j in range(n):
            if zero_row[i] or zero_col[j]:
                matrix[i][j] = 0
    return matrix

Dùng hàng đầu tiên và cột đầu tiên làm dấu mốc

Ý tưởng

Cột đầu tiên có một ô cho mỗi hàng, còn hàng đầu tiên có một ô cho mỗi cột, đúng với hình dạng của hai mảng đánh dấu. Vì vậy, số 0 tại hàng i, cột j sẽ ghi số 0 vào matrix[i][0] và matrix[0][j]. Việc đó không làm mất thông tin nào: mỗi ô trong số đó nằm trên một dòng vốn phải được chuyển thành 0.

Hàng 0 và cột 0 vừa chứa dữ liệu, vừa làm dấu, nên dấu ở đó sẽ che khuất việc chúng có vốn chứa số 0 hay không. Vì vậy, hãy kiểm tra chúng trước và lưu kết quả vào hai biến boolean. Chỉ đánh dấu và điền các ô có i ≥ 1 và j ≥ 1, rồi cuối cùng mới xóa hàng 0 và cột 0, vì bước điền cần đọc chúng.

Trong ví dụ thứ hai, số 3 ở hàng 1, cột 1 vẫn giữ nguyên vì các dấu của nó, matrix[1][0] = 9 và matrix[0][1] = 4, không phải là 0. Độ phức tạp thời gian vẫn là O(m·n), với hai biến boolean làm bộ nhớ phụ (O(m·n) trong R, vì chương trình sao chép đầu vào trước).

Thuật toán

Đặt firstRowZero nếu hàng 0 có giá trị 0 và firstColZero nếu cột 0 có giá trị 0.
Với mỗi ô có i ≥ 1 và j ≥ 1 chứa giá trị 0, đặt matrix[i][0] và matrix[0][j] thành 0.
Với mỗi ô có i ≥ 1 và j ≥ 1, đặt ô đó thành 0 nếu matrix[i][0] hoặc matrix[0][j] bằng 0.
Nếu firstRowZero là đúng, đặt hàng 0 thành 0. Nếu firstColZero là đúng, đặt cột 0 thành 0.
Trả về ma trận.

def setZeroes(matrix):
    m, n = len(matrix), len(matrix[0])
    # The first row and column will hold the markers, so remember first
    # whether they need to become zero themselves.
    first_row_zero = any(matrix[0][j] == 0 for j in range(n))
    first_col_zero = any(matrix[i][0] == 0 for i in range(m))
    # Mark: a zero inside the matrix flags its row in column 0
    # and its column in row 0.
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][j] == 0:
                matrix[i][0] = 0
                matrix[0][j] = 0
    # Fill the inside from the markers.
    for i in range(1, m):
        for j in range(1, n):
            if matrix[i][0] == 0 or matrix[0][j] == 0:
                matrix[i][j] = 0
    # The marker row and column go last.
    if first_row_zero:
        for j in range(n):
            matrix[0][j] = 0
    if first_col_zero:
        for i in range(m):
            matrix[i][0] = 0
    return matrix

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

Xóa một hàng và một cột ngay khi bạn tìm thấy số 0. Trong ví dụ đầu tiên, số 0 mới ở hàng 1, cột 2 sẽ làm xóa cột 2, và chỉ số 3 ở góc trên bên trái còn lại.
Để matrix[0][0] đánh dấu cả hàng 0 lẫn cột 0. Trong [[1, 2, 3], [0, 5, 6], [7, 8, 9]], số 0 ở cột 0 sẽ xóa nhầm hàng 0.
Xóa hàng 0 hoặc cột 0 trước khi điền. Trong [[0, 2, 3], [4, 5, 6], [7, 8, 9]], mọi cột đều có vẻ được đánh dấu, và toàn bộ mảng trở thành 0.
Quên các dòng đơn. Với một hàng, các vòng lặp bắt đầu từ 1 không làm gì cả, còn các giá trị boolean đảm nhiệm toàn bộ công việc: [[1, 0, 3]] phải trở thành [[0, 0, 0]].

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

Tại sao bạn không thể đặt các số không trong lúc quét ma trận?

Số 0 bạn viết trông giống hệt số 0 ban đầu. Khi quá trình quét đến số 0 đó, nó xóa cả hàng và cột chứa nó, rồi những số 0 mới này lan rộng hơn. Hãy ghi lại tất cả số 0 ban đầu trước khi thay đổi bất kỳ ô nào.

Độ phức tạp thời gian của bài toán Đặt các phần tử trong ma trận thành 0 là bao nhiêu?

O(m·n) cho ma trận m × n, vì mỗi ô được đọc và ghi một số lần cố định. Không có lời giải nào hiệu quả hơn, vì bất kỳ ô nào bị bỏ qua cũng có thể là số 0 làm thay đổi kết quả. Bộ nhớ phụ là O(m + n) khi dùng các mảng đánh dấu và O(1) khi dùng hàng đầu tiên và cột đầu tiên làm dấu.

Bạn có thể đánh dấu các ô bằng một giá trị đặc biệt thay vì 0 không?

Một số lời giải ghi một giá trị giữ chỗ vào các ô cần xóa rồi chuyển các giá trị giữ chỗ thành số 0 ở cuối. Cách này chỉ hiệu quả nếu giá trị giữ chỗ không bao giờ xuất hiện trong đầu vào, điều mà một ma trận số nguyên hiếm khi đảm bảo. Việc ghi giá trị đó dọc theo một hàng và một cột cho mỗi số 0 cũng tốn thời gian O(m·n·(m + n)).

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

Kiểm thử #1

Kiểm thử #2

Đối số

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

Đầu ra mong đợi

[[3, 0, 1], [0, 0, 0], [2, 0, 4]]