|
1 | 1 | classSolution { |
2 | 2 | publicint[][]diagonalSort(int[][]mat) { |
3 | | -Map<Integer,PriorityQueue<Integer>>map =newHashMap<>(); |
4 | | -for (inti =0;i <mat.length;i++) { |
5 | | -for (intj =0;j <mat[0].length;j++) { |
6 | | -map.computeIfAbsent(i -j,k ->newPriorityQueue<>()).add(mat[i][j]); |
7 | | - } |
| 3 | +intnumRows =mat.length; |
| 4 | +intnumCols =mat[0].length; |
| 5 | +for (inti =0;i <numRows;i++) { |
| 6 | +sortDiagonal(i,0,mat); |
8 | 7 | } |
9 | | -for (inti =0;i <mat.length;i++) { |
10 | | -for (intj =0;j <mat[0].length;j++) { |
11 | | -mat[i][j] =map.get(i -j).poll(); |
12 | | - } |
| 8 | +for (inti =0;i <numCols;i++) { |
| 9 | +sortDiagonal(0,i,mat); |
13 | 10 | } |
14 | 11 | returnmat; |
15 | 12 | } |
| 13 | + |
| 14 | +privatevoidsortDiagonal(introw,intcol,int[][]mat) { |
| 15 | +intnumRows =mat.length; |
| 16 | +intnumCols =mat[0].length; |
| 17 | +List<Integer>diagonal =newArrayList<>(); |
| 18 | +intdiagonalLength =Math.min(numRows -row,numCols -col); |
| 19 | +for (inti =0;i <diagonalLength;i++) { |
| 20 | +diagonal.add(mat[row +i][col +i]); |
| 21 | + } |
| 22 | +diagonal =countingSort(diagonal); |
| 23 | +for (inti =0;i <diagonalLength;i++) { |
| 24 | +mat[row +i][col +i] =diagonal.get(i); |
| 25 | + } |
| 26 | + } |
| 27 | + |
| 28 | +privateList<Integer>countingSort(List<Integer>list) { |
| 29 | +intmin =1; |
| 30 | +intmax =100; |
| 31 | +intrange =max -min +1; |
| 32 | +int[]frequency =newint[range]; |
| 33 | +for (intnum :list) { |
| 34 | +frequency[num -min]++; |
| 35 | + } |
| 36 | +List<Integer>sortedList =newArrayList<>(); |
| 37 | +for (inti =0;i <range;i++) { |
| 38 | +intcount =frequency[i]; |
| 39 | +while (count-- >0) { |
| 40 | +sortedList.add(i +min); |
| 41 | + } |
| 42 | + } |
| 43 | +returnsortedList; |
| 44 | + } |
16 | 45 | } |