通过检查相邻条目将矩阵中的负条目变为正条目 - 每次传递仅允许某些转换,时间复杂度是多少?
Turning negative entries positive in a matrix by checking adjacent entries- only certain conversions allowed each pass, what's the time complexity?
我得到了 positive and negative integers
的 (nxm)
矩阵。
目标是尝试将所有负数转换为正数,如果可能,return 矩阵的 number of passes
需要执行此操作,否则 return -1
.
规则如下:
- 您只能将负数转换为正数,前提是负数的相邻(正上方、下方、左侧或右侧)条目为正数。
- 如果您在某次传递中将一个数字从负数转换为正数,则您不能使用这个(最近)变成正数来将其他负数变成正数 - 至少对于这次传递。
我已经为该问题编写了一个可接受的解决方案,但我似乎无法计算出该解决方案的 Time Complexity
。
我的解决方案:
创建一个Boolean matrix
来标记在当前pass中已经变成正的负条目(我们会在每次pass之后重置这个矩阵)
迭代矩阵的所有条目
对于我们偶然发现的每个负数,检查其所有 4 个相邻条目,看看是否有任何正数条目。
如果是,将其转换为正数,并在布尔矩阵中标记。
每次遍历整个矩阵时递增 number of passes
。
当我们遍历整个矩阵并且没有对其进行任何更改(即从负到正的转换)时,我们就完成了。
如果还有任何负条目,return -1
,否则return 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
最坏的情况是矩阵的一个角出现正数,而其他所有项均为负数。这将需要 (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 是一个集合。
我得到了 positive and negative integers
的 (nxm)
矩阵。
目标是尝试将所有负数转换为正数,如果可能,return 矩阵的 number of passes
需要执行此操作,否则 return -1
.
规则如下:
- 您只能将负数转换为正数,前提是负数的相邻(正上方、下方、左侧或右侧)条目为正数。
- 如果您在某次传递中将一个数字从负数转换为正数,则您不能使用这个(最近)变成正数来将其他负数变成正数 - 至少对于这次传递。
我已经为该问题编写了一个可接受的解决方案,但我似乎无法计算出该解决方案的 Time Complexity
。
我的解决方案:
创建一个
Boolean matrix
来标记在当前pass中已经变成正的负条目(我们会在每次pass之后重置这个矩阵)迭代矩阵的所有条目
对于我们偶然发现的每个负数,检查其所有 4 个相邻条目,看看是否有任何正数条目。 如果是,将其转换为正数,并在布尔矩阵中标记。
每次遍历整个矩阵时递增
number of passes
。当我们遍历整个矩阵并且没有对其进行任何更改(即从负到正的转换)时,我们就完成了。
如果还有任何负条目,
return -1
,否则returnnumber 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
最坏的情况是矩阵的一个角出现正数,而其他所有项均为负数。这将需要 (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 是一个集合。