Java | LeetCode
Задача: 1380. Lucky Numbers in a Matrix
Сложность: easy
Дана матрица m x n из различных чисел, верните все счастливые числа в матрице в любом порядке.
Счастливое число — это элемент матрицы, который является минимальным элементом в своей строке и максимальным в своем столбце.
Пример:
Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column.
👨💻 Алгоритм:
1⃣Сохраните минимум каждой строки в список rowMin и максимум каждого столбца в список colMax.
2⃣Итерируйте по каждому числу в матрице и проверяйте, равно ли оно rowMin[i] и colMax[j].
3⃣Если число удовлетворяет условию, добавьте его в список luckyNumbers и верните luckyNumbers.
😎 Решение:
class Solution {
public List<Integer> luckyNumbers (int[][] matrix) {
int N = matrix.length;
int M = matrix[0].length;
List<Integer> rowMin = new ArrayList<>();
for (int i = 0; i < N; i++) {
int rMin = Integer.MAX_VALUE;
for (int j = 0; j < M; j++) {
rMin = Math.min(rMin, matrix[i][j]);
}
rowMin.add(rMin);
}
List<Integer> colMax = new ArrayList<>();
for (int i = 0; i < M; i++) {
int cMax = Integer.MIN_VALUE;
for (int j = 0; j < N; j++) {
cMax = Math.max(cMax, matrix[j][i]);
}
colMax.add(cMax);
}
List<Integer> luckyNumbers = new ArrayList<>();
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
if (matrix[i][j] == rowMin.get(i) && matrix[i][j] == colMax.get(j)) {
luckyNumbers.add(matrix[i][j]);
}
}
}
return luckyNumbers;
}
}
Ставь 👍 и забирай 📚 Базу знаний
1 · 272 ·