难度: Hard
Submission
运行时间: 236 ms
内存: 46.9 MB
class UnionFind:
def __init__(self, n: int) -> None:
self.root_or_size = [-1] * n
self.part = n
return
def find(self, x):
y = x
while self.root_or_size[x] >= 0:
# range_merge_to_disjoint to the direct root node after query
x = self.root_or_size[x]
while y != x:
self.root_or_size[y], y = x, self.root_or_size[y]
return x
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
if self.root_or_size[root_x] < self.root_or_size[root_y]:
root_x, root_y = root_y, root_x
self.root_or_size[root_y] += self.root_or_size[root_x]
self.root_or_size[root_x] = root_y
self.part -= 1
return True
def union_left(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
self.root_or_size[root_x] += self.root_or_size[root_y]
self.root_or_size[root_y] = root_x
self.part -= 1
return True
def union_right(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
self.root_or_size[root_y] += self.root_or_size[root_x]
self.root_or_size[root_x] = root_y
self.part -= 1
return True
def is_connected(self, x, y):
return self.find(x) == self.find(y)
def get_node_size(self, x):
return -self.root_or_size[self.find(x)]
def get_root_part(self):
# get the nodes list of every root
part = defaultdict(list)
n = len(self.root_or_size)
for i in range(n):
part[self.find(i)].append(i)
return part
def get_root_size(self):
# get the size of every root
size = defaultdict(int)
n = len(self.root_or_size)
for i in range(n):
if self.find(i) == i:
size[i] = -self.root_or_size[i]
return size
class Solution:
def amountPainted(self, paint: List[List[int]]) -> List[int]:
m = max(ls[1] for ls in paint) + 10
uf = UnionFind(m)
ans = []
for a, b in paint:
cnt = 0
a = uf.find(a)
while a < b:
cnt += 1
uf.union_right(a, a + 1)
a = uf.find(a + 1)
ans.append(cnt)
return ans
Explain
题解使用了并查集(Union-Find)来动态管理和合并区间。每次绘制时，从区间的起始点开始，尝试将该点与其右侧相邻点合并，并递归地进行此操作直至区间末端。如果一个点已经被绘制，则此操作会将该点与之前已绘制区域的根节点合并，从而避免重复绘制。这种方法通过并查集高效地处理了区间合并问题，并实时计算每次操作绘制的新区域数量。
时间复杂度: O(n*k)
空间复杂度: O(m)
class UnionFind:
def __init__(self, n: int) -> None:
self.root_or_size = [-1] * n # 初始化n个节点的根为自身且大小为-1
self.part = n # 初始时各节点独立
return
def find(self, x):
y = x
while self.root_or_size[x] >= 0:
x = self.root_or_size[x]
while y != x:
self.root_or_size[y], y = x, self.root_or_size[y]
return x
def union(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
if self.root_or_size[root_x] < self.root_or_size[root_y]:
root_x, root_y = root_y, root_x
self.root_or_size[root_y] += self.root_or_size[root_x]
self.root_or_size[root_x] = root_y
self.part -= 1
return True
def union_left(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
self.root_or_size[root_x] += self.root_or_size[root_y]
self.root_or_size[root_y] = root_x
self.part -= 1
return True
def union_right(self, x, y):
root_x = self.find(x)
root_y = self.find(y)
if root_x == root_y:
return False
self.root_or_size[root_y] += self.root_or_size[root_x]
self.root_or_size[root_x] = root_y
self.part -= 1
return True
def is_connected(self, x, y):
return self.find(x) == self.find(y)
def get_node_size(self, x):
return -self.root_or_size[self.find(x)]
def get_root_part(self):
part = defaultdict(list)
n = len(self.root_or_size)
for i in range(n):
part[self.find(i)].append(i)
return part
def get_root_size(self):
size = defaultdict(int)
n = len(self.root_or_size)
for i in range(n):
if self.find(i) == i:
size[i] = -self.root_or_size[i]
return size
class Solution:
def amountPainted(self, paint: List[List[int]]) -> List[int]:
m = max(ls[1] for ls in paint) + 10 # 计算需要的并查集大小
uf = UnionFind(m)
ans = []
for a, b in paint:
cnt = 0
a = uf.find(a)
while a < b:
cnt += 1 # 统计新增绘制的区域数
uf.union_right(a, a + 1) # 将当前点与右侧点合并
a = uf.find(a + 1)
ans.append(cnt)
return ans
Explore
在确定并查集的大小m时，题解中计算了所有绘制区间的最大结束位置，并对其增加了10作为缓冲。这样做是为了确保即使在最大索引附近还有操作也能被处理。这种方法在实际应用中通常足够安全，尤其是在没有明确的最大值限制时，适当的缓冲可以避免索引越界错误。
常规的union方法将两个节点合并时，通常基于树的高度或大小来优化，以减少查找的深度。而union_right方法特别设计为将当前节点与其右侧节点合并，这符合绘制区域时从左至右的合并需求。在此题中，使用union_right可以直观地映射绘制过程中的逐点合并操作，同时保证并查集结构的连续性和合理性。
这种从起始点向末端尝试合并的方法能有效处理重叠区间。通过并查集的快速合并和查找操作，可以在绘制过程中快速判断哪些部分已被绘制，并避免重复绘制。虽然每次操作都需要从区间的起点开始检查至终点，可能会有一定的性能损耗，但由于路径压缩和按秩合并的优化，整体效率仍然是可接受的。
路径压缩是一种优化技术，通过在每次查找过程中将查找路径上的所有节点直接连接到根节点，从而压缩路径长度并减少后续操作的时间复杂度。这种技术显著提高了并查集的效率，使得几乎所有操作都能在几乎常数时间内完成，极大地提高了数据结构的性能，尤其是在处理大量元素和查询的情况下非常有效。