网站建设一般好久到期,谁给推荐一个免费的好网站,什么样的企业要做网站,产品型网站案例其他系列文章导航 Java基础合集数据结构与算法合集 设计模式合集 多线程合集 分布式合集 ES合集 文章目录
其他系列文章导航
文章目录
前言
一、题目描述
二、题解
三、代码
四、复杂度分析 前言
这是力扣的2661题#xff0c;难度为中等#xff0c;解题方案有很多种难度为中等解题方案有很多种本文讲解我认为最奇妙的一种。 一、题目描述
给你一个下标从 0 开始的整数数组 arr 和一个 m x n 的整数 矩阵 mat 。arr 和 mat 都包含范围 [1m * 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;HashMapInteger, 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(vectorint arr, vectorvectorint mat) {int n mat.size(), m mat[0].size();unordered_mapint, pairint, int map;for (int i 0; i n; i) {for (int j 0; j m; j) {map[mat[i][j]] make_pair(i, j);}}vectorint c1(n), c2(m);for (int i 0; i n * m; i) {pairint, 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] * mfor i in range(n * m):x, y mapping[arr[i]]c1[x], c2[y] c1[x] 1, c2[y] 1if c1[x] m or c2[y] n: return ireturn -1 # never四、复杂度分析
时间复杂度O(n×m)空间复杂度O(n×m)
