JavaScript实现Set Matrix Zeroes算法的性能优化咨询

Great question! Your current implementation works, but as you've noticed, the repeated row/column traversals every time you hit a 0 can add up to unnecessary overhead—especially for larger matrices. Let's break down how to optimize this while keeping the in-place requirement intact.

First, Let's Analyze Your Current Approach #

Your code uses a marker ('X') to flag elements that need to be set to 0 later, which is clever for avoiding extra space. However:

• Time Complexity: Worst-case scenario (when the matrix is full of 0s), this runs in O(mn(m+n)) time—each 0 triggers a full traversal of its row and column, leading to redundant work.
• Redundant Marking: If multiple 0s exist in the same row or column, you'll re-mark the same elements over and over.

The Optimized Approach: Use the Matrix's Own Borders for Tracking #

Instead of traversing rows/columns every time you find a 0, we can repurpose the first row and first column of the matrix to store which rows and columns need to be set to 0. This keeps space complexity at O(1) (no extra arrays) and reduces time complexity to O(mn)—a single pass to mark, then a pass to set zeros.

Here's the step-by-step logic:

1. Check if the first row or column has any zeros: We need to track this separately because we'll overwrite these borders with our markers.
2. Mark rows and columns using the first row/column: Traverse the matrix starting from the second row and second column. If an element matrix[i][j] is 0, set matrix[0][j] = 0 (mark column j to be zeroed) and matrix[i][0] = 0 (mark row i to be zeroed).
3. Zero out marked rows and columns: Use the markers in the first row/column to set all elements in the corresponding rows and columns to 0.
4. Zero out the first row/column if needed: Use the boolean flags we set earlier to handle the first row and column themselves.

Optimized Code Implementation #

var setZeroes = function(matrix) {
    if (!matrix || matrix.length === 0) return;
    
    const rows = matrix.length;
    const cols = matrix[0].length;
    let firstRowHasZero = false;
    let firstColHasZero = false;

    // Step 1: Check if first row/column has zeros
    for (let j = 0; j < cols; j++) {
        if (matrix[0][j] === 0) {
            firstRowHasZero = true;
            break;
        }
    }
    for (let i = 0; i < rows; i++) {
        if (matrix[i][0] === 0) {
            firstColHasZero = true;
            break;
        }
    }

    // Step 2: Mark rows and columns using first row/column
    for (let i = 1; i < rows; i++) {
        for (let j = 1; j < cols; j++) {
            if (matrix[i][j] === 0) {
                matrix[i][0] = 0;
                matrix[0][j] = 0;
            }
        }
    }

    // Step 3: Zero out marked rows and columns
    for (let i = 1; i < rows; i++) {
        if (matrix[i][0] === 0) {
            for (let j = 1; j < cols; j++) {
                matrix[i][j] = 0;
            }
        }
    }
    for (let j = 1; j < cols; j++) {
        if (matrix[0][j] === 0) {
            for (let i = 1; i < rows; i++) {
                matrix[i][j] = 0;
            }
        }
    }

    // Step 4: Handle first row and column
    if (firstRowHasZero) {
        for (let j = 0; j < cols; j++) {
            matrix[0][j] = 0;
        }
    }
    if (firstColHasZero) {
        for (let i = 0; i < rows; i++) {
            matrix[i][0] = 0;
        }
    }
};

Why This Is Better #

• Time Efficiency: We only traverse the matrix a constant number of times (3 full passes + 2 checks for the first row/column), leading to O(mn) time complexity—much faster than the original approach for large matrices.
• Space Efficiency: No extra arrays or markers like 'X' needed; we use the matrix's own space, keeping O(1) auxiliary space.
• No Redundant Work: Each element is processed exactly once during marking, and rows/columns are only zeroed once based on the markers.

内容的提问来源于stack exchange，提问作者myTest532 myTest532