查询后矩阵的和

标签: 数组 哈希表

难度: Medium

给你一个整数 n 和一个下标从 0 开始的 二维数组 queries ，其中 queries[i] = [typei, indexi, vali] 。

一开始，给你一个下标从 0 开始的 n x n 矩阵，所有元素均为 0 。每一个查询，你需要执行以下操作之一：

  • 如果 typei == 0 ，将第 indexi 行的元素全部修改为 vali ，覆盖任何之前的值。
  • 如果 typei == 1 ，将第 indexi 列的元素全部修改为 vali ，覆盖任何之前的值。

请你执行完所有查询以后，返回矩阵中所有整数的和。

示例 1：

输入：n = 3, queries = [[0,0,1],[1,2,2],[0,2,3],[1,0,4]]
输出：23
解释：上图展示了每个查询以后矩阵的值。所有操作执行完以后，矩阵元素之和为 23 。

示例 2：

输入：n = 3, queries = [[0,0,4],[0,1,2],[1,0,1],[0,2,3],[1,2,1]]
输出：17
解释：上图展示了每一个查询操作之后的矩阵。所有操作执行完以后，矩阵元素之和为 17 。

提示：

  • 1 <= n <= 104
  • 1 <= queries.length <= 5 * 104
  • queries[i].length == 3
  • 0 <= typei <= 1
  • 0 <= indexi < n
  • 0 <= vali <= 105

Submission

运行时间: 103 ms

内存: 33.9 MB

class Solution:
    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:
        hang,lie=set(),set()
        ans=0
        for a,b,c in reversed(queries):
            if a==0:
                if b not in hang:
                    ans+=c*(n-len(lie))    
                    hang.add(b)
            else:
                if b not in lie:
                    ans+=c*(n-len(hang))
                    lie.add(b)
        return ans

Explain

本题解采用了一种避免直接构建和修改矩阵的优化方法。首先初始化两个集合 hang 和 lie，分别用来记录所有已被修改过的行和列。同时，用一个变量 ans 来累计矩阵中所有元素的和。遍历查询数组 queries，从后向前处理每个查询，判断当前查询的类型（修改行或列）。如果是修改行且此行未被修改过，则将该行所有元素加上新值，但要减去已被修改的列中对应的元素。同理，如果是修改列且此列未被修改过，则将该列所有元素加上新值，但要减去已被修改的行中对应的元素。这种方法有效避免了重复计算已被修改过的行或列，每次修改只考虑新增加的部分。

时间复杂度: O(m)

空间复杂度: O(n)

# 定义一个类 Solution

class Solution:
    def matrixSumQueries(self, n: int, queries: List[List[int]]) -> int:
        hang, lie = set(), set()  # 初始化行和列的集合
        ans = 0  # 初始化答案变量
        for a, b, c in reversed(queries):  # 从后向前遍历查询
            if a == 0:  # 如果是行操作
                if b not in hang:  # 检查该行是否被处理过
                    ans += c * (n - len(lie))  # 更新答案，加上新值乘以未被修改的列的数量
                    hang.add(b)  # 标记该行已处理
            else:  # 如果是列操作
                if b not in lie:  # 检查该列是否被处理过
                    ans += c * (n - len(hang))  # 更新答案，加上新值乘以未被修改的行的数量
                    lie.add(b)  # 标记该列已处理
        return ans  # 返回答案

Explore

从后向前处理查询的主要原因是为了避免多次修改同一行或列导致重复计算。通过从后向前的处理方式，可以确保当我们第一次遇到某行或列的修改时，即为该行或列的最终修改，此时将修改效果一次性计算并记录，避免了之后再次处理该行或列时重复计算的问题。这种方法更加高效，因为它保证了每一行或列只被计算一次。

在处理行或列的修改时，通过使用集合 hang 和 lie 来跟踪哪些行和列已经被修改过，确保不会对同一行或列进行重复计算。当对某行进行修改时，如果该行已存在于集合 hang 中，则不再进行处理；同理，对某列的处理也会检查集合 lie。这样，每次修改只考虑未被修改过的行或列，从而避免了重复计算。

算法通过确保每个行或列只在其首次出现在查询中时被处理来保证最终的和是正确的。由于查询是从后向前处理的，因此在处理某个行或列的查询时，我们可以保证这是对该行或列的最后一次修改（即最终状态）。通过这种方式，算法只处理每个行或列的最终修改效果，即使它们在查询数组中多次出现。

使用集合 hang 和 lie 跟踪修改的行和列是一种空间换时间的策略，能够显著减少不必要的重复计算。在处理大量 queries 时，虽然存储空间消耗会增加（每个集合最多存储 n 个元素），但是时间效率会得到很大的提升，因为每个查询最多只处理一次。这种方法特别适合处理那些包含大量重复行或列修改的查询数组，因为它可以极大地减少计算量。