Every day a Leetcode

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

解法1：哈希

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

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

算法：

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

結果：

復雜度分析：

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

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