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

Question

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

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

以下是规则：

• 如果负数有一个相邻的(正上方、下方、左侧或右侧(条目为正数，则只能将负数转换为正数
• 如果在某个过程中将一个数字从负数转换为正数，则不能使用这个(最近(转换的正数将其他负数转换为负数-至少在该过程中是这样

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

我的解决方案：

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

2. 迭代矩阵的所有条目

3. 对于每一个负数，我们都会偶然发现它的所有4个相邻条目，看看是否有正数。如果是，请将其转换为正，并在布尔矩阵中进行标记。

4. 每次迭代整个矩阵时，递增number of passes。

5. 当我们在整个矩阵上迭代，并且没有对其进行任何更改(即从负到正的转换(时，我们就完成了。

6. 如果还有任何负条目，则返回return -1，否则返回number of passes。

我似乎想不出最坏的情况了——对这个解决方案的时间复杂性有什么建议吗？我最初的想法是，它是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(，因为nextWords是一个集合