Java | LeetCode
Задача: 1329. Sort the Matrix Diagonally
Сложность: medium
Диагональ матрицы — это диагональная линия ячеек, начинающаяся с какой-либо ячейки в самой верхней строке или в самом левом столбце и идущая в направлении вниз-вправо до конца матрицы. Например, диагональ матрицы, начинающаяся с mat[2][0], где mat — это матрица размером 6 x 3, включает ячейки mat[2][0], mat[3][1] и mat[4][2].
Дана матрица mat размером m x n, состоящая из целых чисел. Отсортируйте каждую диагональ матрицы по возрастанию и верните полученную матрицу.
Пример:
Input: mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]]
Output: [[1,1,1,1],[1,2,2,2],[1,2,3,3]]
👨💻 Алгоритм:
1⃣Сохраните размеры матрицы m и n. Создайте хеш-карту из минимальных куч для хранения элементов диагоналей.
2⃣Вставьте значения в хеш-карту, используя разность между индексами строки и столбца как ключ, чтобы собирать элементы на одной и той же диагонали.
3⃣Извлеките значения из хеш-карты и обновите матрицу, заполняя ее отсортированными значениями диагоналей. Верните отсортированную матрицу.
😎 Решение:
class Solution {
public int[][] diagonalSort(int[][] mat) {
int m = mat.length;
int n = mat[0].length;
Map<Integer, PriorityQueue<Integer>> diagonals = new HashMap<>();
for (int row = 0; row < m; row++) {
for (int col = 0; col < n; col++) {
int key = row - col;
diagonals.putIfAbsent(key, new PriorityQueue<>());
diagonals.get(key).add(mat[row][col]);
}
}
for (int row = 0; row < m; row++) {
for (int col = 0; col < n; col++) {
int key = row - col;
mat[row][col] = diagonals.get(key).poll();
}
}
return mat;
}
}
Ставь 👍 и забирай 📚 Базу знаний
1 · 450 ·