###### tags: `Leetcode` `medium` `hash` `heap` `python`

# 1329. Sort the Matrix Diagonally

## [題目連結:] https://leetcode.com/problems/sort-the-matrix-diagonally/

## 題目:
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.


#### [圖片來源:] https://leetcode.com/problems/sort-the-matrix-diagonally/

## 解題想法:
* 要求matrix按照對角線進行重新排序
* 技巧: **對於同一對角線上，(i,j)座標差是相同的**
* 使用dic:
* key:對角線座標的差值
* val:出現在其座標的所有數，以list存
* dic中每個list皆以heapq排序(由小至大)
* 最終按照每個位置依序heappop()出

## Python:

from collections import defaultdict
from heapq import heappush, heappop
class Solution(object):
    def diagonalSort(self, mat):
        """
        :type mat: List[List[int]]
        :rtype: List[List[int]]
        """
        m=len(mat)
        n=len(mat[0])
        dic=defaultdict(list) #key: 座標差值 val: 符合差值的座標值
        #將對角值依序存入dic
        for i in range(m):
            for j in range(n):
                diff=i-j
                heappush(dic[diff],mat[i][j])
        #重新填入mat
        for i in range(m):
            for j in range(n):
                diff=i-j
                mat[i][j]=heappop(dic[diff])
        return mat

if __name__=='__main__':
    result=Solution()
    ans=result.diagonalSort(mat = [[3,3,1,1],[2,2,1,2],[1,1,1,2]])
    print(ans)
    '''
    [[1, 1, 1, 1], 
     [1, 2, 2, 2], 
     [1, 2, 3, 3]]
    '''