目录链接:
力扣编程题-解法汇总_分享+记录-CSDN博客
>https://blog.csdn.net/rzleilei/article/details/121477931?spm=1001.2014.3001.5502
GitHub同步刷题项目:
https://github.com/September26/java-algorithms
>https://github.com/September26/java-algorithms
原题链接:
描述:
给你一个下标从
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 <= 105
-
1 <= m * n <= 105
-
1 <= arr[i], mat[r][c] <= m * n
-
arr
中的所有整数
互不相同
-
mat
中的所有整数
互不相同
解题思路:
最简单的方式,自然是按照题目的描述,每插入一个数字都检查一次,但是这样时间复杂度比较高。所以我们可以反向思考一下,针对整个矩阵,横向和纵向分别遍历一行或者一列,每次找出最大的那个位置。
每次遍历一行或者一列得出的位置中,找出最小的那个。
代码:
class Solution {
public int firstCompleteIndex(int[] arr, int[][] mat) {
Map<Integer, Integer> indexMap = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
indexMap.put(arr[i], i);
}
int minValue = Integer.MAX_VALUE;
for (int i = 0; i < mat.length; i++) {
int itemMinValue = 0;
for (int j = 0; j < mat[i].length; j++) {
itemMinValue = Math.max(itemMinValue, indexMap.get(mat[i][j]));
}
minValue = Math.min(minValue, itemMinValue);
}
System.out.println("minValue:" + minValue);
for (int j = 0; j < mat[0].length; j++) {
int itemMinValue = 0;
for (int i = 0; i < mat.length; i++) {
itemMinValue = Math.max(itemMinValue, indexMap.get(mat[i][j]));
}
minValue = Math.min(minValue, itemMinValue);
}
return minValue;
}
}