題目連結:
題目意譯:
你被給定一個索引值從 0 開始數的整數陣列 arr 以及一個大小為 m × n 的整數矩陣 mat。arr 和 mat 兩者都包含位於範圍 [1, m × n] 中的所有整數。
掃過 arr 中每一個索引值 i(從索引值 0 開始)來把 arr[i] 位於 mat 中的那一格格子塗上顏色。
回傳最小的索引值 i 使得 mat 中某一列或某一行是全部都有塗上顏色的。
限制:
m == mat.length
n = mat[i].length
arr.length == m × n
1 ≦ m, n ≦ 10 ^ 5
1 ≦ m × n ≦ 10 ^ 5
1 ≦ arr[i], mat[r][c] ≦ m × n
arr 中的整數彼此相異。
mat 中的整數彼此相異。
範例測資:
範例 1:
輸入: arr = [1,3,4,2], mat = [[1,4],[2,3]]
輸出: 2
解釋: 上圖展示了塗色的順序,而矩陣中第一列以及第二行在 arr[2] 時變成全部都有塗色的狀態。
範例 2:
輸入: arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]
輸出: 3
解釋: 第二行在 arr[3] 的時候變成全部都有塗色。
解題思維:
用四個陣列——一個統計每一列各自出現的整數數量、一個則是統計每一行的出現整數數量,另外兩個則是紀錄每一個 arr[i] 在 mat 中出現的行號以及列號(以便方便塗色),並模擬即可。
而當某一列(或行)的出現整數數量等於總行數(或總列數)時,代表著矩陣中該列(行)是有全部被上色的。此時的索引值 i 即為所求。
此次分享到此為止,如有任何更加簡潔的想法或是有說明不清楚之地方,也煩請各位大大撥冗討論。