Cracking the Coding Interview-1.8

第六版Cracking the Coding Interview题目1.8，题目如下：

Zero Matrix: Write an algorithm such that if an element in an MxN matrix is 0, its entire row and column are set to O.

问题看起来非常简单，但是不难想到如果在历遍矩阵时就进行就地清零将会影响到对其他值的判断。比如若矩阵中只有第一个值为0，循环过程中整个矩阵都会被清零。所以需要借助额外的储存空间记录需要被清零的位置，其中比较简单的方法就是记录需要被清零的行号和列号。以下Python代码中借助numpy来简化和加快计算过程：

import numpy as np
def zeroMatrix(matrix):
    matrix = np.array(matrix)
    m, n = matrix.shape
    rows, cols = [], []

    # Store the row and column index with value 0
    for i in xrange(m):
        for j in xrange(n):
            if matrix[i, j] == 0:
                rows.append(i)
                cols.append(j)

    # Nullify rows
    for i in rows:
        matrix[i] = np.zeros(n)

    # Nullify columns
    for j in cols:
        matrix[:, j] = np.zeros(m)

    return matrix

虽然上述代码已经非常简洁了，但是若矩阵中0的数量为k，该方法依旧需要O(k)的空间。若需要空间复杂度为O(1)的算法的话，便需要借助矩阵的第一行和第一列来记录需要清零的行和列。但是在这种方法中，必需先记录第一行和第一列中是否包含0以免修改其中元素后造成判断错误。详细实现如下：

# Python 2.7
import numpy as np
def zeroMatrix(matrix):
    matrix = np.array(matrix)
    m, n = matrix.shape

    # Check if first row has a zero
    rowHasZero = not np.all(matrix[0])

    # Check if first column has a zero
    colHaszero = not np.all(matrix[:, 0])

    # Check for zeros in the rest of the array
    for i in xrange(1, m):
        for j in xrange(1, n):
            if matrix[i, j] == 0:
                matrix[i, 0] = 0
                matrix[0, j] = 0

    # Nullify rows
    for i in xrange(1,m):
        if matrix[i, 0] == 0:
            matrix[i,1:] = np.zeros(n-1)

    # Nullify columns
    for j in xrange(1,n):
        if matrix[0, j] == 0:
            matrix[1:, j] = np.zeros(m-1)

    # Nullify first row
    if rowHasZero:
        matrix[0] = np.zeros(n)

    # Nullify first column
    if colHaszero:
        matrix[:, 0] = np.zeros(m)

    return matrix

可以发现这种方法虽然节省了空间，但循环的次数较多一些。

在手机上阅读或分享本文请扫描以下二维码：

Cracking the Coding Interview-1.8

Comments