LeetCode 2661. First Completely Painted Row or Column
周賽343。題目讀起來有點繞口,要翻譯還真不太好翻。
題目Permalink
輸入整數陣列array,還有m*n的整數矩陣mat。
兩者都正好由[1, m*n]之間的整數所組成。
從arr的索引0開始,逐一將mat中編號為arr[i]的格子上色。
求最小的索引i,滿足arr[i]對應的格子上色後,使某行或列的所有格子都被上色。
解法Permalink
由於mat中的元素都是唯一的,可以直接以mat[r][c]的值為鍵,映射到(r,c)上。
兩個陣列row和col紀錄個行列的上色次數。遍歷arr[i],將對應到的行列次數加1,若使得某列達到N、或某行達到M次上色,則答案為i。
時間複雜度O(MN)。
空間複雜度O(MN)。
class Solution:
def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int:
M,N=len(mat),len(mat[0])
mp={}
for r in range(M):
for c in range(N):
mp[mat[r][c]]=[r,c]
row=[0]*M
col=[0]*N
for i,x in enumerate(arr):
r,c=mp[x]
row[r]+=1
col[c]+=1
if row[r]==N or col[c]==M:
return i