嘉定网站设计制作价格,ppt模板免费下载 素材第一ppt,wordpress 1.5.2,网站简繁体转换jsEvery day a Leetcode
题目来源#xff1a;2661. 找出叠涂元素
解法1#xff1a;哈希
题目很绕#xff0c;理解题意后就很简单。
由于矩阵 mat 中每一个元素都不同#xff0c;并且都在数组 arr 中#xff0c;所以首先我们用一个哈希表 hash 来存储 mat 中每一个元素的…Every day a Leetcode
题目来源2661. 找出叠涂元素
解法1哈希
题目很绕理解题意后就很简单。
由于矩阵 mat 中每一个元素都不同并且都在数组 arr 中所以首先我们用一个哈希表 hash 来存储 mat 中每一个元素的位置信息即行列信息。然后用一个长度为 m 的数组来表示每一行中已经被涂色的个数用一个长度为 n 的数组来表示每一列中已经被涂色的个数。其中若出现某一行 i 出现 rowsCount[i]n 或者某一列 j 出现 colsCount[j]m则表示第 i 行或者第 j 列都被涂色。
算法
特判。mat 的行数为 m列数为 n。建立一个哈希表 unordered_mapint, pairint, int hash其中 key 是 mat 中整数值value 是一个 pairint, int存储的是 mat 中 key 值的横坐标、纵坐标。遍历 mat其中 key mat[i][j]pairint, int value(i, j)插入哈希表 hash 中。用一个长度为 m 的数组 rowsCount 来表示每一行中已经被涂色的个数用一个长度为 n 的数组 colsCount 来表示每一列中已经被涂色的个数遍历数组 arr设下标为 i找到 arr[i] 在 mat 中的横纵坐标row hash[arr[i]].firstcol hash[arr[i]].second计数数组对应的行列自增 1如果发现 rowsCount[row] n说明第 row 行的 n 个单元格都被涂上色返回此时的下标 i同理如果发现 colsCount[col] m说明第 col 列的 m 个单元格都被涂上色返回此时的下标 i。
代码
/** lc appleetcode.cn id2661 langcpp** [2661] 找出叠涂元素*/// lc codestart
class Solution
{
public:int firstCompleteIndex(vectorint arr, vectorvectorint mat){if (arr.empty() || mat.empty())return -1;int m mat.size(), n m ? mat[0].size() : 0;unordered_mapint, pairint, int hash; // 整数pair横坐标纵坐标for (int i 0; i m; i)for (int j 0; j n; j){int key mat[i][j];pairint, int value(i, j);hash[key] value;}vectorint rowsCount(m, 0), colsCount(n, 0);for (int i 0; i arr.size(); i){int row hash[arr[i]].first, col hash[arr[i]].second;rowsCount[row];if (rowsCount[row] n)return i;colsCount[col];if (colsCount[col] m)return i;}return -1;}
};
// lc codeend结果 复杂度分析
时间复杂度O(m*n)其中 m 和 n 分别是二维数组 mat 的行数和列数。主要为用哈希表存储矩阵 mat 中每一个元素对应行列序号的时间开销。
空间复杂度O(m*n)其中 m 和 n 分别是二维数组 mat 的行数和列数。主要为用哈希表存储矩阵 mat 中每一个元素对应行列序号的空间开销。
