leetcode

0 class Solution {

1 public:

2 vector<vector<int>> diagonalSort(vector<vector<int>> &mat) {

3 unordered_map<int, priority_queue<int, vector<int>, greater<int>>> um;

4 int n = mat.size(), m = mat[0].size();

5 for (int i = 0; i < n; i++) {

6 for (int j = 0; j < m; j++) {

7 um[i - j].push(mat[i][j]);

8 }

9 }

10

11 for (int i = 0; i < n; i++) {

12 for (int j = 0; j < m; j++) {

13 mat[i][j] = um[i - j].top();

14 um[i - j].pop();

15 }

16 }

17

18 return mat;

19 }

20 };

21

22 // No extra memory

23 class Solution {

24 public:

25 vector<vector<int>> diagonalSort(vector<vector<int>> &mat) {

26 int n = mat.size(), m = mat[0].size();

27 for (int k = 0; k < m; k++) {

28 for (int i = 0, ik = k; i < n && ik < m; i++, ik++) {

29 for (int j = 0, jk = k; j < n && jk < m; j++, jk++) {

30 if (mat[i][ik] < mat[j][jk]) swap(mat[i][ik], mat[j][jk]);

31 }

32 }

33 }

34

35 for (int k = 0; k < n; k++) {

36 for (int i = 0, ik = k; i < m && ik < n; i++, ik++) {

37 for (int j = 0, jk = k; j < m && jk < n; j++, jk++) {

38 if (mat[ik][i] < mat[jk][j]) swap(mat[ik][i], mat[jk][j]);

39 }

40 }

41 }

42

43 return mat;

44 }

45 };