1329. Sort the Matrix Diagonally

1329. Sort the Matrix Diagonally

Question

A matrix diagonal is a diagonal line of cells starting from some cell in either the topmost row or leftmost column and going in the bottom-right direction until reaching the matrix’s end. For example, the matrix diagonal starting from mat[2][0], where mat is a 6 x 3 matrix, includes cells mat[2][0], mat[3][1], and mat[4][2].

Given an m x n matrix mat of integers, sort each matrix diagonal in ascending order and return the resulting matrix.

Solution

分别遍历数组的两条边。
按对角线顺序进行遍历,用列表记录访问过的数字。
排序列表后按对角线填入原数组。

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
class Solution {
public int[][] diagonalSort(int[][] mat) {
int m = mat.length, n = mat[0].length;
List<Integer> arr = new ArrayList<>();

for(int t = 0; t < m; t++){
int i = t, j = 0;

while(i < m && j < n){
arr.add(mat[i][j]);
i++;
j++;
}

Collections.sort(arr);

i = t;
j = 0;

while(i < m && j < n){
mat[i][j] = arr.get(j);
i++;
j++;
}
arr.clear();
}

for(int t = 1; t < n; t++){
int i = 0, j = t;

while(i < m && j < n){
arr.add(mat[i][j]);
i++;
j++;
}

Collections.sort(arr);

i = 0;
j = t;

while(i < m && j < n){
mat[i][j] = arr.get(i);
i++;
j++;
}
arr.clear();
}
return mat;
}
}
Author

Xander

Posted on

2022-08-27

Updated on

2022-08-27

Licensed under

Comments