2661.md

title	description	keywords
2661. 找出叠涂元素	LeetCode 2661. 找出叠涂元素题解，First Completely Painted Row or Column，包含解题思路、复杂度分析以及完整的 JavaScript 代码实现。	LeetCode 2661. 找出叠涂元素 找出叠涂元素 First Completely Painted Row or Column 解题思路 数组 哈希表 矩阵

2661. 找出叠涂元素

🟠 Medium  🔖  数组 哈希表 矩阵  🔗 力扣 LeetCode

题目

You are given a 0-indexed integer array arr, and an m x n integer matrix mat. arr and mat both contain all the integers in the range [1, m * n].

Go through each index i in arr starting from index 0 and paint the cell in mat containing the integer arr[i].

Return the smallest index i at which either a row or a column will be completely painted in mat.

Example 1:


Input: arr = [1,3,4,2], mat = [[1,4],[2,3]]

Output: 2

Explanation: The moves are shown in order, and both the first row and second column of the matrix become fully painted at arr[2].

Example 2:

Input: arr = [2,8,7,4,1,3,5,6,9], mat = [[3,2,5],[1,4,6],[8,7,9]]

Output: 3

Explanation: The second column becomes fully painted at arr[3].

Constraints:

• m == mat.length
• n = mat[i].length
• arr.length == m * n
• 1 <= m, n <= 10^5
• 1 <= m * n <= 10^5
• 1 <= arr[i], mat[r][c] <= m * n
• All the integers of arr are unique.
• All the integers of mat are unique.

题目大意

给你一个下标从 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.length
• n = mat[i].length
• arr.length == m * n
• 1 <= m, n <= 10^5
• 1 <= m * n <= 10^5
• 1 <= arr[i], mat[r][c] <= m * n
• arr 中的所有整数 互不相同
• mat 中的所有整数 互不相同

解题思路

1. 预处理：构建位置映射

   • 将矩阵的每个值的行、列索引记录到一个哈希表中，以便快速找到 arr[i] 在矩阵中的位置。

2. 初始化计数数组

   • 使用两个数组 rowCount 和 colCount 分别记录矩阵中每一行和每一列已涂色的单元格数。

3. 模拟涂色过程

   • 遍历 arr，对于每个值，根据映射找到其在矩阵中的行和列索引。
   • 更新对应的 rowCount 和 colCount。
   • 检查当前行或列是否完全涂满，如果是，直接返回当前的操作步骤。

复杂度分析

• 时间复杂度：O(m * n + k)
  • 预处理位置映射：O(m * n)，其中 m 和 n 分别是矩阵的行数和列数。
  • 模拟涂色过程：O(k)，k 是 arr 的长度。
  • 总复杂度为 O(m * n + k)。
• 空间复杂度：O(m + n + m*n)，使用了两个计数数组 rowCount 和 colCount，以及一个映射表。

代码

/**
 * @param {number[][]} grid
 * @param {number[]} arr
 * @return {number}
 */
var firstCompleteIndex = function (grid, arr) {
	const m = grid.length,
		n = grid[0].length;

	// 映射每个值到它在矩阵中的位置
	const valueToPosition = new Map();
	for (let i = 0; i < m; i++) {
		for (let j = 0; j < n; j++) {
			valueToPosition.set(grid[i][j], [i, j]);
		}
	}

	// 初始化行和列的计数器
	const rowCount = new Array(m).fill(0);
	const colCount = new Array(n).fill(0);

	// 遍历数组，模拟涂色
	for (let step = 0; step < arr.length; step++) {
		const value = arr[step];
		const [row, col] = valueToPosition.get(value);

		// 更新行和列的计数
		rowCount[row]++;
		colCount[col]++;

		// 检查是否有行或列被完全涂满
		if (rowCount[row] === n || colCount[col] === m) {
			return step; // 返回从 0 开始的索引
		}
	}
};

相关题目

题号	标题	题解	标签	难度	力扣
2133	检查是否每一行每一列都包含全部整数	[✓]	数组 哈希表 矩阵	🟢	🀄️ 🔗
2482	行和列中一和零的差值		数组 矩阵 模拟	🟠	🀄️ 🔗