制作游戏网站,沙漠风网站建设6,wordpress仿微信公众号模板,微站开发文章目录 Tag题目来源题目解读解题思路方法一#xff1a;哈希表 写在最后 Tag
【哈希表】【数组】【2023-12-01】 题目来源
2661. 找出叠涂元素 题目解读
从左往右遍历 arr 给矩阵 mat 上色#xff0c;在上色的过程中矩阵的某一行或者某一列的全部被上色了#xff0c;返回… 文章目录 Tag题目来源题目解读解题思路方法一哈希表 写在最后 Tag
【哈希表】【数组】【2023-12-01】 题目来源
2661. 找出叠涂元素 题目解读
从左往右遍历 arr 给矩阵 mat 上色在上色的过程中矩阵的某一行或者某一列的全部被上色了返回此时的 i。 解题思路
本题难度不大就是题目意思有点不容易理解相信大家在理解了我的题目解读之后就会明白题目的含义。
方法一哈希表
为方便表述记 n 为矩阵 mat 的行数m 为矩阵的列数。
整体思路
我们需要判断某一行或者某一列是否被全部涂色如是则返回让这一行或者这一列被全部涂色的最后一个整数在数组 arr 中对应的下标。
于是我们需要遍历数组 arr看看是哪一个下标对应的整数将矩阵 mat 的某一行或某一列涂满色。
首先需要使用哈希表或者数组来统计mat中每一个整数对应的行和列下方代码中使用的是数组 num2Idx 来统计数组的下标表示mat中的整数值对应 i * m ji 表示整数在 mat 中的行索引j 表示列索引。还要维护两个数组 rowCnt 和 colCntrowCnt[i] 表示矩阵第 i 行被涂色的格子数colCnt 表示矩阵第 j 行被涂色的格子数。
接着从左往右遍历数组 arr 中的整数 num根据 num2Idx[num] 更新数组 rowCnt 和 colCnt如果某一行或者某一列被涂满色则返回 num 在 arr 中的索引。
实现代码
class Solution {
public:int firstCompleteIndex(vectorint arr, vectorvectorint mat) {int n mat.size(), m mat[0].size();vectorint num2Idx(n * m 1);for (int i 0; i n; i) {for (int j 0; j m; j) {num2Idx[mat[i][j]] i * m j;}}vectorint rowCnt(n, 0), colCnt(m, 0);for (int i 0; i arr.size(); i) {int num arr[i];int row num2Idx[num] / m, col num2Idx[num] % m;if (rowCnt[row] m) {return i;}if (colCnt[col] n) {return i;}}return -1;}
};复杂度分析
时间复杂度 O ( n × m ) O(n \times m) O(n×m) n n n 是矩阵 mat 的宽度 m m m 是矩阵的高度。
空间复杂度 O ( n × m ) O(n \times m) O(n×m)。 写在最后
如果文章内容有任何错误或者您对文章有任何疑问欢迎私信博主或者在评论区指出 。
如果大家有更优的时间、空间复杂度方法欢迎评论区交流。
最后感谢您的阅读如果感到有所收获的话可以给博主点一个 哦。
