今日题目

https://leetcode.com/problems/first-completely-painted-row-or-column/description

思路

按照题目要求模拟即可。

技巧

可以为每行和每列分别维护一个计数数组，从而随时掌握任意行或列中已涂色的格子数量。

方法

  1. 记录网格中每个数字所在的位置。
  2. 每次涂色时，对应行和列的计数各加一。
  3. 若某次涂色使某一行或某一列全部涂满，则返回当前下标 i。

复杂度

  • 时间复杂度：$O(NM)$，N、M 分别为网格的行数和列数。

  • 空间复杂度：$O(NM)$，需要存储每个数字的位置索引。

代码

class Solution:
    def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
        col = [0] * (len(arr) + 1)
        row = [0] * (len(arr) + 1)
        for i in range(len(mat)):
            for j in range(len(mat[0])):
                col[mat[i][j]] = j
                row[mat[i][j]] = i
    
        cntR,cntC = [0] * len(mat), [0] * len(mat[0])

        for i, x in enumerate(arr):
            cntR[row[x]] += 1
            cntC[col[x]] += 1
            if cntR[row[x]] == len(mat[0]) or cntC[col[x]] == len(mat):
                return i
        
        return -1

image.png