498.md

498 Diagonal Traverse

Description

link

---

Solution

• 先把所有i+ j + 1相同的数字排列在一起，如果是奇数层，反转，否则直接添加

---

Code

O(m + n)

class Solution:
    def findDiagonalOrder(self, matrix: List[List[int]]) -> List[int]:
        result = [ ]
        dd = collections.defaultdict(list)
        if not matrix: return result
        # Step 1: Numbers are grouped by the diagonals.
        # Numbers in same diagonal have same value of row+col
        for i in range(0, len(matrix)):
            for j in range(0, len(matrix[0])):
                dd[i+j+1].append(matrix[i][j]) # starting indices from 1, hence i+j+1.
        # Step 2: Place diagonals in the result list.
        # But remember to reverse numbers in odd diagonals.
        for k in sorted(dd.keys()):
            if k%2==1: dd[k].reverse()
            result += dd[k]
        return result