找出叠涂元素
难度:
标签:
题目描述
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.lengthn = mat[i].lengtharr.length == m * n1 <= m, n <= 1051 <= m * n <= 1051 <= arr[i], mat[r][c] <= m * n- All the integers of
arrare unique. - All the integers of
matare unique.
代码结果
运行时间: 124 ms, 内存: 37.5 MB
/*
题目思路：
1. 初始化两个数组 rows 和 cols 用于记录每行和每列涂色的单元格数。
2. 使用一个 Map 来存储 mat 中每个数值的坐标位置。
3. 使用 Stream API 来遍历 arr，查找对应数值在 mat 中的位置，并更新 rows 和 cols 数组。
4. 检查当前行或列是否全部涂色，如果是则返回当前索引。
*/
import java.util.HashMap;
import java.util.Map;
import java.util.stream.IntStream;
public class Solution {
public int firstCompleteIndex(int[] arr, int[][] mat) {
int m = mat.length;
int n = mat[0].length;
int[] rows = new int[m];
int[] cols = new int[n];
Map<Integer, int[]> positionMap = new HashMap<>();
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
positionMap.put(mat[i][j], new int[]{i, j});
}
}
return IntStream.range(0, arr.length).filter(i -> {
int num = arr[i];
int[] pos = positionMap.get(num);
int row = pos[0];
int col = pos[1];
rows[row]++;
cols[col]++;
return rows[row] == n || cols[col] == m;
}).findFirst().orElse(-1);
}
}解释
方法:
题解的思路是通过建立矩阵元素到其索引的映射，然后通过遍历数组 arr 检查每个元素涂色时矩阵的行或列是否完全涂满。具体来说，首先建立一个 idx 数组，使 idx[v] 存储值 v 在矩阵 mat 中的线性索引。接着，定义两个数组 row_cnt 和 column_cnt 来跟踪每行和每列未被涂色的单元格数量。遍历 arr，每次涂色后更新对应行和列的未涂色计数，一旦某行或某列的计数降至0，即表示该行或列完全涂满，此时返回当前元素的索引。
时间复杂度:
O(m * n)
空间复杂度:
O(m * n)
代码细节讲解
🦆
在建立idx数组时，你是如何确保每个元素的值都能在数组中找到正确的索引？
▷🦆
为什么选择使用单独的row_cnt和column_cnt数组来跟踪未涂色的单元格数量，而不是直接修改mat矩阵？
▷🦆
当row_cnt或column_cnt中某个值减到0时，你是如何确保这一行或一列确实已经完全被涂色的？
▷🦆
在算法中，如果arr数组中的某些值重复出现，会对算法的行为或最终结果产生什么影响？
▷