Every day a Leetcode

題目來源：2661. 找出疊涂元素

解法1：哈希

題目很繞，理解題意后就很簡單。

由于矩陣 mat 中每一個元素都不同，并且都在數(shù)組 arr 中，所以首先我們用一個哈希表 hash 來存儲 mat 中每一個元素的位置信息（即行列信息）。然后用一個長度為 m 的數(shù)組來表示每一行中已經(jīng)被涂色的個數(shù)，用一個長度為 n 的數(shù)組來表示每一列中已經(jīng)被涂色的個數(shù)。其中若出現(xiàn)某一行 i 出現(xiàn) rowsCount[i]=n 或者某一列 j 出現(xiàn) colsCount[j]=m，則表示第 i 行或者第 j 列都被涂色。

算法：

1. 特判。
2. mat 的行數(shù)為 m，列數(shù)為 n。
3. 建立一個哈希表 unordered_map<int, pair<int, int>> hash，其中 key 是 mat 中整數(shù)值，value 是一個 pair<int, int>，存儲的是 mat 中 key 值的橫坐標(biāo)、縱坐標(biāo)。
4. 遍歷 mat，其中 key = mat[i][j]，pair<int, int> value(i, j)，插入哈希表 hash 中。
5. 用一個長度為 m 的數(shù)組 rowsCount 來表示每一行中已經(jīng)被涂色的個數(shù)，用一個長度為 n 的數(shù)組 colsCount 來表示每一列中已經(jīng)被涂色的個數(shù)
6. 遍歷數(shù)組 arr，設(shè)下標(biāo)為 i，找到 arr[i] 在 mat 中的橫縱坐標(biāo)：row = hash[arr[i]].first，col = hash[arr[i]].second，計(jì)數(shù)數(shù)組對應(yīng)的行列自增 1，如果發(fā)現(xiàn) rowsCount[row] = n，說明第 row 行的 n 個單元格都被涂上色，返回此時的下標(biāo) i；同理，如果發(fā)現(xiàn) colsCount[col] = m，說明第 col 列的 m 個單元格都被涂上色，返回此時的下標(biāo) i。

代碼：

/** @lc app=leetcode.cn id=2661 lang=cpp** [2661] 找出疊涂元素*/// @lc code=start
class Solution
{
public:int firstCompleteIndex(vector<int> &arr, vector<vector<int>> &mat){if (arr.empty() || mat.empty())return -1;int m = mat.size(), n = m ? mat[0].size() : 0;unordered_map<int, pair<int, int>> hash; // <整數(shù)，pair<橫坐標(biāo)，縱坐標(biāo)>>for (int i = 0; i < m; i++)for (int j = 0; j < n; j++){int key = mat[i][j];pair<int, int> value(i, j);hash[key] = value;}vector<int> 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 code=end

結(jié)果：

復(fù)雜度分析：

時間復(fù)雜度：O(m*n)，其中 m 和 n 分別是二維數(shù)組 mat 的行數(shù)和列數(shù)。主要為用哈希表存儲矩陣 mat 中每一個元素對應(yīng)行列序號的時間開銷。

空間復(fù)雜度：O(m*n)，其中 m 和 n 分別是二維數(shù)組 mat 的行數(shù)和列數(shù)。主要為用哈希表存儲矩陣 mat 中每一個元素對應(yīng)行列序號的空間開銷。