Mind palace

some thoughts

0%

498. Diagonal Traverse

Posted on Edited on In Disqus:
Symbols count in article: 2.1k Reading time ≈ 2 mins.

O(mn)↗↙
0 <= sum < m + n - 1
0 <= r < n
0 <= c < m
sum = r + c
0 <= r = sum - c < n即sum - n < c <= sum
0 <= c = sum - r < m即sum - m < r <= sum
所以
max(0, sum - m + 1) <= r <= min(n - 1, sum)
// max(0, sum - n + 1) <= c <= min(m - 1, sum)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        int R = matrix.size(), C = matrix[0].size();
        vector<int> res;
        int size = R + C - 1;
        for (int sum = 0; sum < size; ++sum) {
            if (sum & 1) {
                for (int r = max(0, sum - (C - 1)); r <= min(R - 1, sum); ++r) {
                    res.push_back(matrix[r][sum - r]);
                }
            } else {
                for (int r = min(R - 1, sum); r >= max(0, sum - (C - 1)); --r) {
                    res.push_back(matrix[r][sum - r]);
                }
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        int n = matrix.size(), m = matrix[0].size();
        vector<int> res;
        int size = m + n - 1;
        for (int sum = 0; sum < size; ++sum) {
            if (sum & 1) {
                for (int r = max(0, sum - m + 1); r <= min(n - 1, sum); ++r) {
                    res.push_back(matrix[r][sum - r]);
                }
            } else {
                for (int c = max(0, sum - n + 1); c <= min(m - 1, sum); ++c) {
                    res.push_back(matrix[sum - c][c]);
                }
            }
        }
        return res;
    }
};

O(n2)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    vector<int> findDiagonalOrder(vector<vector<int>>& matrix) {
        int row_size = matrix.size();
        int col_size = row_size > 0 ? matrix.front().size() : 0;
        int max_size = row_size + col_size - 1;
        vector<int> ret;
        for (int i = 0; i < max_size; ++i) { // i is the sum of row + col
            if (i & 1) {
						// 0 <= i - row < col_size && 0 <= row < row_size
                for (int row = max(i - col_size + 1, 0); row < min(i + 1, row_size); ++row) {
                    ret.push_back(matrix[row][i - row]);
                }
            }
            else {
						// 0 <= i - col < row_size && 0 <= col < col_size
                for (int col = max(i - row_size + 1, 0); col < min(i + 1, col_size); ++col) {
                    ret.push_back(matrix[i - col][col]);
                }
            }
        }
        return ret;
    }
};