找出叠涂元素

标签: 数组 哈希表 矩阵

难度: Medium

给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数 矩阵 mat 。arr 和 mat 都包含范围 [1，m * n] 内的 所有 整数。

从下标 0 开始遍历 arr 中的每个下标 i ，并将包含整数 arr[i] 的 mat 单元格涂色。

请你找出 arr 中第一个使得 mat 的某一行或某一列都被涂色的元素，并返回其下标 i 。

示例 1：

image explanation for example 1 
输入：arr = [1,3,4,2], mat = [[1,4],[2,3]]
输出：2
解释：遍历如上图所示，arr[2] 在矩阵中的第一行或第二列上都被涂色。

示例 2：

image explanation for example 2 
输入：arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]
输出：3
解释：遍历如上图所示，arr[3] 在矩阵中的第二列上都被涂色。

提示：

  • m == mat.length
  • n = mat[i].length
  • arr.length == m * n
  • 1 <= m, n <= 105
  • 1 <= m * n <= 105
  • 1 <= arr[i], mat[r][c] <= m * n
  • arr 中的所有整数 互不相同
  • mat 中的所有整数 互不相同

Submission

运行时间: 124 ms

内存: 37.5 MB

class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])
        idx = [0] * (m*n+1)
        for i in range(m):
            for j in range(n):
                idx[mat[i][j]] = i*n+j
        row_cnt = [n] * m
        column_cnt = [m] * n
        for i, v in enumerate(arr):
            x, y = idx[v]//n, idx[v]%n
            row_cnt[x] -= 1
            column_cnt[y] -= 1
            if row_cnt[x] == 0 or column_cnt[y] == 0:
                return i

Explain

题解的思路是通过建立矩阵元素到其索引的映射，然后通过遍历数组 arr 检查每个元素涂色时矩阵的行或列是否完全涂满。具体来说，首先建立一个 idx 数组，使 idx[v] 存储值 v 在矩阵 mat 中的线性索引。接着，定义两个数组 row_cnt 和 column_cnt 来跟踪每行和每列未被涂色的单元格数量。遍历 arr，每次涂色后更新对应行和列的未涂色计数，一旦某行或某列的计数降至0，即表示该行或列完全涂满，此时返回当前元素的索引。

时间复杂度: O(m * n)

空间复杂度: O(m * n)

class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        m, n = len(mat), len(mat[0])  # 矩阵的行数和列数
        idx = [0] * (m*n+1)  # 存储每个值在矩阵中的索引
        for i in range(m):
            for j in range(n):
                idx[mat[i][j]] = i*n+j  # 填充 idx 数组
        row_cnt = [n] * m  # 初始化每行未涂色计数
        column_cnt = [m] * n  # 初始化每列未涂色计数
        for i, v in enumerate(arr):
            x, y = idx[v]//n, idx[v]%n  # 计算值 v 在矩阵中的行列索引
            row_cnt[x] -= 1  # 更新行计数
            column_cnt[y] -= 1  # 更新列计数
            if row_cnt[x] == 0 or column_cnt[y] == 0:  # 检查是否有行或列完全涂满
                return i  # 返回该元素的索引

Explore

在建立idx数组时，我通过遍历矩阵mat的每一个元素，并将每个元素的值作为idx数组的索引，其在矩阵中的线性索引作为值。这样，每个元素的值v都直接对应到其在矩阵中的位置（i*n+j），其中i是行索引，j是列索引，n是矩阵的列数。这种映射方式要求矩阵mat中的每个值都是唯一的，且不超过m*n，其中m和n分别是矩阵的行数和列数。

使用单独的row_cnt和column_cnt数组来跟踪每行和每列的未涂色单元格数量是为了保持原矩阵mat的数据不变，这样可以避免破坏原始数据结构。此外，通过使用这两个计数数组，算法可以更加高效地计算和更新每行和每列的未涂色单元格数量，而直接修改mat矩阵则可能需要更复杂的逻辑来跟踪哪些元素已被修改。

当算法中的row_cnt[x]或column_cnt[y]减至0时，这意味着对应的行x或列y的所有单元格都已经被涂色，因为每次在涂色一个单元格时，相应的行和列的计数器都会减1。初始化时，row_cnt数组的每个元素被设置为该行的单元格总数，column_cnt数组的每个元素被设置为该列的单元格总数。因此，当这些计数器减到0，表示对应的行或列的单元格已经完全被涂色。

如果arr数组中的某些值重复出现，算法会对每个出现的值按顺序进行处理，即便这意味着同一个矩阵位置可能被多次考虑涂色。然而，即使重复涂色，行和列的计数器只在首次达到0时影响结果，之后的重复值不会再次触发行或列计数为0的情况。因此，重复的值可能会导致某些不必要的计算，但不会改变首次完全涂满行或列时返回的索引。