通过检查相邻的条目，在矩阵中将负项变为正项--只有某些转换允许每次传递，那么时间复杂度是多少？

Question

给出了(nxm)矩阵的positive and negative integers。

目标是尝试将所有负数转换为正数，如果可能的话，返回所需矩阵的number of passes，否则是return -1。

以下是规则：

• 只能将负数转换为正数，如果负数有一个相邻的(正上方、下、左或右)条目是正的。如果在某一关中将一个数字从负数转换为正数，那么您就不能使用这个(最近)变成正数的数字来将其他负数变为正数--至少对于这一关是这样的。

我已经为这个问题写了一个可接受的解决方案，但我似乎无法计算出解决方案的Time Complexity。

我的解决方案：

1. 创建一个Boolean matrix来标记在当前传递中已变为正的负面条目(我们将在每次传递后重置此矩阵)

1. 迭代矩阵

的所有条目。

，

1. ，对于每个负数，我们偶然发现，检查它的所有4个相邻条目，看看是否有正数。如果是，则将其转换为正，并在布尔矩阵.

中标记它。

每次我们迭代整个矩阵时，

1. 增量number of passes。

当我们对整个矩阵进行迭代而没有对其进行任何更改(即从负到正的转换)时，就完成了

1. 。

如果仍然存在任何负项，则返回number of passes.，否则返回

1. 。

我似乎想不出最坏的情况--对这个解决方案的时间复杂性有什么建议吗？我最初的想法是，它是O(n)，其中n是矩阵的大小。

作为参考，以下是我的解决方案：

def minimumPassesOfMatrix(matrix):
    numberOfPasses = 0
    ChangesMade = True

    while ChangesMade:
        negToPosMarket = [[False for _ in range(len(matrix[0]))] for _ in range(len(matrix))]
        ChangesMade = False
        for row in range(len(matrix)):
            for col in range(len(matrix[0])):
                if matrix[row][col] < 0:
                    positiveAdjacent = checkAdjacentEntriesForPositive(matrix, row, col, negToPosMarket)
                    if positiveAdjacent:
                        matrix[row][col] *= -1
                        negToPosMarket[row][col] = True
                        ChangesMade = True
        if not ChangesMade:
            break
        numberOfPasses += 1

    if all(matrix[row][col] >= 0 for row in range(len(matrix)) for col in range(len(matrix[0]))):  #notebook double for loop list comp!
        return numberOfPasses

    print(matrix)

    return -1


def checkAdjacentEntriesForPositive(matrix, row, col, negToPosMarket):
    matrixHeight = len(matrix) - 1
    matrixWidth = len(matrix[0]) - 1

    if not OutOfBounds(row + 1, col, matrixHeight, matrixWidth) and not negToPosMarket[row + 1][col]:
        if matrix[row + 1][col] > 0:
            return True
    if not OutOfBounds(row - 1, col, matrixHeight, matrixWidth) and not negToPosMarket[row - 1][col]:
        if matrix[row - 1][col] > 0:
            return True
    if not OutOfBounds(row, col + 1, matrixHeight, matrixWidth) and not negToPosMarket[row][col + 1]:
        if matrix[row][col + 1] > 0:
            return True
    if not OutOfBounds(row, col - 1, matrixHeight, matrixWidth) and not negToPosMarket[row][col - 1]:
        if matrix[row][col - 1] > 0:
            return True

    return False


def OutOfBounds(row, col, matrixHeight, matrixWidth):
    return row < 0 or col < 0 or row > matrixHeight or col > matrixWidth

Answer 1

最坏的情况是矩阵某个角落的正数，其他的都是负数。这将需要(n+m-2)传球来翻转相反的角.如果每次遍历每个位置，那么时间复杂性将是(n+m)xnxm。

如果使用一组坐标，则可以将其简化为nxm。

将正值的坐标放置在一个集合中。在每一次传递时，将其负邻居转换为正，并将这些前负值的坐标放置到下一次传递的新集合中。这样，您只处理每一项一次。

下面是Python中的一个示例：

def makePos(matrix):
    m = len(matrix)
    n = len(matrix[0])
    plusCoords = {(r,c) for r,row in enumerate(matrix)
                        for c,val in enumerate(row)
                        if val>0} # initial set of + coordinates    
    passes = 0
    iterations = 0
    while plusCoords:      # more passes for new + coordinates
        passes += 1        # count passes
        nextCoords = set() # coordinates of new positives 
        for r,c in plusCoords: # go through this pass's coords
            iterations += 1
            for dr,dc in [(-1,0),(0,-1),(0,1),(1,0)]: # neigbors
                nr,nc = r+dr, c+dc
                if nr not in range(m): continue
                if nc not in range(n): continue
                if matrix[nr][nc] < 0:           # flip to positive
                    nextCoords.add((nr,nc))      # track flips
        for nr,nc in nextCoords:   
            matrix[nr][nc] *= -1         # update matrix
        plusCoords = nextCoords          # coords for next pass
    return passes - 1, iterations

                            # passes
M = [ [10,-1,-1,-1,-1],     # 0 1 2 3 4
      [-1,-1,-1,-1,-1],     # 1 2 3 4 5
      [-1,-1,-1,-1,-1]]     # 2 3 4 5 6 

print(*makePos(M))  # 6 15  (6 passes,15 iterations)

注意，for dr,dc in [(-1,0),(0,-1),(0,1),(1,0)]:循环在这里算作O(1)，因为它为r，c坐标做了固定量的工作。nextCoords.add((nr,nc))函数是O(1)，因为nextCoords是一个集合。