描述绘画结果

标签: 数组 哈希表 前缀和 排序

难度: Medium

给你一个细长的画，用数轴表示。这幅画由若干有重叠的线段表示，每个线段有 独一无二 的颜色。给你二维整数数组 segments ，其中 segments[i] = [starti, endi, colori] 表示线段为 半开区间 [starti, endi) 且颜色为 colori 。

线段间重叠部分的颜色会被 混合 。如果有两种或者更多颜色混合时，它们会形成一种新的颜色，用一个 集合 表示这个混合颜色。

  • 比方说，如果颜色 2 ，4 和 6 被混合，那么结果颜色为 {2,4,6} 。

为了简化题目，你不需要输出整个集合，只需要用集合中所有元素的 和 来表示颜色集合。

你想要用 最少数目 不重叠 半开区间 来 表示 这幅混合颜色的画。这些线段可以用二维数组 painting 表示，其中 painting[j] = [leftj, rightj, mixj] 表示一个 半开区间[leftj, rightj) 的颜色 和 为 mixj 。

  • 比方说，这幅画由 segments = [[1,4,5],[1,7,7]] 组成，那么它可以表示为 painting = [[1,4,12],[4,7,7]] ，因为：
    • [1,4) 由颜色 {5,7} 组成（和为 12），分别来自第一个线段和第二个线段。
    • [4,7) 由颜色 {7} 组成，来自第二个线段。

请你返回二维数组 painting ，它表示最终绘画的结果（没有 被涂色的部分不出现在结果中）。你可以按 任意顺序 返回最终数组的结果。

半开区间 [a, b) 是数轴上点 a 和点 b 之间的部分，包含 点 a 且 不包含 点 b 。

示例 1：

输入：segments = [[1,4,5],[4,7,7],[1,7,9]]
输出：[[1,4,14],[4,7,16]]
解释：绘画结果可以表示为：
- [1,4) 颜色为 {5,9} （和为 14），分别来自第一和第二个线段。
- [4,7) 颜色为 {7,9} （和为 16），分别来自第二和第三个线段。

示例 2：

输入：segments = [[1,7,9],[6,8,15],[8,10,7]]
输出：[[1,6,9],[6,7,24],[7,8,15],[8,10,7]]
解释：绘画结果可以以表示为：
- [1,6) 颜色为 9 ，来自第一个线段。
- [6,7) 颜色为 {9,15} （和为 24），来自第一和第二个线段。
- [7,8) 颜色为 15 ，来自第二个线段。
- [8,10) 颜色为 7 ，来自第三个线段。

示例 3：

输入：segments = [[1,4,5],[1,4,7],[4,7,1],[4,7,11]]
输出：[[1,4,12],[4,7,12]]
解释：绘画结果可以表示为：
- [1,4) 颜色为 {5,7} （和为 12），分别来自第一和第二个线段。
- [4,7) 颜色为 {1,11} （和为 12），分别来自第三和第四个线段。
注意，只返回一个单独的线段 [1,7) 是不正确的，因为混合颜色的集合不相同。

提示：

  • 1 <= segments.length <= 2 * 104
  • segments[i].length == 3
  • 1 <= starti < endi <= 105
  • 1 <= colori <= 109
  • 每种颜色 colori 互不相同。

Submission

运行时间: 436 ms

内存: 35.8 MB

class Solution:
    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:
        points = defaultdict(lambda: 0)
        for s, e, c in segments:
            points[s] += c
            points[e] -= c
            # print(points)
        # 对所有的点进行排序
        sorted_points = sorted(points.keys())
        res = []
        # 遍历每个线段
        cur = 0
        for s, e in zip(sorted_points[:-1], sorted_points[1:]):
            cur += points[s]
            if cur != 0:
                tmp = [s, e, cur]
                res.append(tmp)
        # print(points, sorted_points)
        return res

Explain

题解采用了扫描线算法和差分的技巧来处理线段的重叠问题。首先，使用一个哈希表（这里是 defaultdict）来存储每个点的颜色差分，其中线段的起始点加上颜色值，终点减去颜色值。通过这种方式，可以标记每个区间的开始和结束对总颜色的贡献。之后，对所有的点进行排序，以便按顺序处理。遍历排序后的点，通过累加前缀和的方式计算从当前点开始的颜色总和，如果这个总和不为零，就将当前点到下一个点的区间以及颜色总和作为结果的一部分。这样可以确保我们正确地构建出了非重叠的区间，每个区间代表的是一种颜色的混合状态。

时间复杂度: O(n + m log m)

空间复杂度: O(m)

class Solution:
    def splitPainting(self, segments: List[List[int]]) -> List[List[int]]:
        points = defaultdict(lambda: 0)  # 存储每个点的颜色差分
        for s, e, c in segments:  # 遍历每个线段
            points[s] += c  # 线段起始点增加颜色值
            points[e] -= c  # 线段结束点减去颜色值
        sorted_points = sorted(points.keys())  # 对所有的点进行排序
        res = []  # 结果数组
        cur = 0  # 当前颜色和
        for s, e in zip(sorted_points[:-1], sorted_points[1:]):  # 遍历排序后的点
            cur += points[s]  # 更新当前颜色和
            if cur != 0:  # 如果当前颜色和不为零，说明有涂色
                res.append([s, e, cur])  # 添加到结果中
        return res

Explore

差分和扫描线算法在处理线段重叠问题时具有简单直观和空间效率高的优势。通过差分方法，我们只需要在线段的起始点和终点进行操作，这种方法可以有效降低算法的复杂度。相比之下，线段树虽然可以高效处理区间的查询和更新，但在实现上更为复杂，且空间消耗也较大。并查集主要用于处理集合合并和查询问题，对于区间重叠和颜色合并的问题并不是特别适用。因此，考虑到问题的特性和算法的效率，选择使用差分和扫描线算法是更合适的。

为了确保只记录有效的颜色变化，可以在处理输入的线段数据时进行验证和预处理。首先，确保每个线段的起始点小于终点，这样可以避免记录无效的或错误的线段。其次，通过哈希表记录颜色差分时，仅在起始点增加颜色值，终点减去颜色值，确保每个点的变化是基于有效的线段输入。此外，在实际计算颜色总和时，通过累加前缀和并检查当前颜色是否为零，可以进一步验证颜色的变化是否有效。这样的方法可以最小化输入错误对最终结果的影响。

排序点的操作能够帮助我们按照一定的顺序处理每个点，从而有效地构建非重叠的区间。通过对所有线段的起始点和终点进行排序，我们可以确保在遍历这些点时，按照从左到右的顺序逐个处理，这样就能保证区间的连续性和正确性。在遍历过程中，通过累加前缀和来计算从当前点开始的颜色总和，只有当这个总和不为零时，我们才将当前点到下一个点的区间作为结果的一部分。这种方法依赖于点的顺序，确保了结果中的区间是按正确的顺序和正确的颜色值构建的。