难度: Medium
Submission
运行时间: 356 ms
内存: 24.6 MB
class Solution:
def sumRemoteness(self, grid: List[List[int]]) -> int:
n = len(grid)
totalSum = totalNum = 0
parts = []
q = deque()
for rr, row in enumerate(grid):
for c in range(n):
v = row[c]
if v > 0:
partSum, partNum = v, 1
row[c] = -1
q.append([rr,c])
while q:
r, c = q.popleft()
for nr, nc in [(r, c-1), (r, c+1), (r-1, c), (r+1,c)]:
if nr < 0 or nr >= n or nc < 0 or nc >= n or grid[nr][nc] < 0:
continue
partSum += grid[nr][nc]
partNum += 1
grid[nr][nc] = -1
q.append([nr, nc])
totalSum += partSum
totalNum += partNum
parts.append((partSum, partNum))
res = 0
for partSum, partNum in parts:
res += (totalSum - partSum)*partNum
return res
Explain
这个题解首先遍历了给定的网格(grid)，对每个元素进行处理。如果发现一个正值的元素，就将其视为一个部分(part)的起始点，然后使用广度优先搜索(BFS)来标记和累加这个部分中所有连通的元素的值，并计算这部分的元素个数。在搜索过程中，每访问一个元素，就将其值设置为-1，以防重复访问。每个部分的总和和元素数量被记录下来。最后，通过比较每个部分的总和和总元素数量与整个网格的总和和总元素数量，计算出所有单元格的远离程度之和。
时间复杂度: O(n^2)
空间复杂度: O(n^2)
class Solution:
def sumRemoteness(self, grid: List[List[int]]) -> int:
n = len(grid) # 网格的边长
totalSum = totalNum = 0 # 初始化总和和总数
parts = [] # 存储每个部分的总和和元素数量
q = deque() # 用于BFS的队列
for rr, row in enumerate(grid):
for c in range(n):
v = row[c]
if v > 0: # 发现一个新的部分的起始点
partSum, partNum = v, 1 # 初始化这个部分的总和和数量
row[c] = -1 # 标记为已访问
q.append([rr,c])
while q: # BFS开始
r, c = q.popleft()
for nr, nc in [(r, c-1), (r, c+1), (r-1, c), (r+1,c)]:
if nr < 0 or nr >= n or nc < 0 or nc >= n or grid[nr][nc] < 0:
continue
partSum += grid[nr][nc]
partNum += 1
grid[nr][nc] = -1
q.append([nr, nc])
totalSum += partSum # 更新总和
totalNum += partNum # 更新总元素数量
parts.append((partSum, partNum)) # 记录这个部分
res = 0
for partSum, partNum in parts: # 计算结果
res += (totalSum - partSum) * partNum
return res
Explore
在BFS中将元素值设置为-1是用来标记该元素已经被访问过，防止在同一次搜索中重复访问同一个元素。这样做有助于确保搜索只处理每个元素一次，避免无限循环或重复计算，从而提高算法的效率和准确性。
为了确保不访问网格外的元素，算法在尝试访问一个新位置之前会检查该位置是否有效。具体的判断包括检查行索引(nr)和列索引(nc)是否在有效范围内，即0 <= nr < n 和 0 <= nc < n，其中n是网格的大小。如果这些条件不满足，就跳过对该位置的处理。
如果网格中存在孤立的正值元素，算法会将其视为一个单独的部分。在BFS的过程中，由于这个元素四周没有其他连接的正值元素，队列中不会添加新元素，因此BFS会在访问这一个元素后结束。该元素的值和数量（1个）会被记录为一个部分的总和和元素数量。
在处理完所有部分后，算法使用每个部分的总和(partSum)和元素数量(partNum)以及整个网格的总和(totalSum)和总元素数量(totalNum)来计算所有单元格的远离程度之和。具体的计算公式为：对每个部分，计算(totalSum - partSum) * partNum，然后将所有部分的这个计算结果累加起来。这样做的目的是量化每个部分与剩余部分的差异，并根据每个部分的元素数量加权这种差异。