其他系列文章导航
文章目录
前言
这是力扣的2661题，难度为中等，解题方案有很多种，本文讲解我认为最奇妙的一种。
一、题目描述
给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数 矩阵mat 。arr 和 mat 都包含范围 [1，m * n] 内的 所有 整数。
从下标 0 开始遍历 arr 中的每个下标 i ，并将包含整数 arr[i] 的 mat 单元格涂色。
请你找出 arr 中在 mat 的某一行或某一列上都被涂色且下标最小的元素，并返回其下标 i 。
示例 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] 在矩阵中的第二列上都被涂色。
提示：
m == mat.lengthn = mat[i].lengtharr.length == m * n1 <= m, n <= 1051 <= m * n <= 1051 <= arr[i], mat[r][c] <= m * narr中的所有整数 互不相同mat中的所有整数 互不相同
二、题解
这道题其实是常规哈希表的运用，本题也将用 HashMap 来借题。
算法：
- 因为 mat 的值各不相同，将用HashMap来存储，以mat[i][j]也就是值为键，[i,j]也就是坐标为值，方便后续快速查询某个值所在位置。
- 然后创建数组 c1 和 c2 ，分别用来记录某行某列有多少单元格被涂色，如
c1[x] = a代表第 x 行被涂色单元格数量为 a 个，c2[y] = b代表第 y 列被涂色单元格数量为 b 个。 - 接着遍历所有的 arr[i] ，查询到 arr[i] 的所在位置 info 后，更新 c1 和 c2，若某行或某列被完全涂色，返回当前下标。
注意题目的意思是：返回刚好涂完一列或一行的时候的最小数字下标。
三、代码
Java版本：
class Solution { public int firstCompleteIndex(int[] arr, int[][] mat) { int n = mat.length, m = mat[0].length; HashMap<Integer, int[]> map = new HashMap<>(); for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { map.put(mat[i][j], new int[]{i, j});//mat[i][j]性质等于arr[i] } } int[] c1 = new int[n], c2 = new int[m];//c1记录某行单元格涂色情况，c1记录某列单元格涂色情况 for (int i = 0; i < n * m; i++) { int[] info = map.get(arr[i]);//info[0]是行坐标，[info[1]]是列坐标 if (++c1[info[0]] == m || ++c2[info[1]] == n) { return i;//第一个叠涂完成的一定是最小的元素 } } return -1; } }
C++版本：
class Solution { public: int firstCompleteIndex(vector<int>& arr, vector<vector<int>>& mat) { int n = mat.size(), m = mat[0].size(); unordered_map<int, pair<int, int>> map; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { map[mat[i][j]] = make_pair(i, j); } } vector<int> c1(n), c2(m); for (int i = 0; i < n * m; i++) { pair<int, int> info = map[arr[i]]; if (++c1[info.first] == m || ++c2[info.secon] == n) return i; } return -1; // never } };
Python版本：
class Solution: def firstCompleteIndex(self, arr: List[int], mat: List[List[int]]) -> int: n, m = len(mat), len(mat[0]) mapping = {mat[i][j]: (i, j) for i in range(n) for j in range(m)} c1, c2 = [0] * n, [0] * m for i in range(n * m): x, y = mapping[arr[i]] c1[x], c2[y] = c1[x] + 1, c2[y] + 1 if c1[x] == m or c2[y] == n: return i return -1 # never
四、复杂度分析
- 时间复杂度：O(n×m)
- 空间复杂度：O(n×m)
