2023-11-22

Leetcode 1424 - Diagonal Traverse II

Problem#

給你一個二維的整數陣列 nums 問你能不能照對角順序輸出（左下到右上）。

測資限制#

$1 \le n, m \le 10^5$
$1 \le \text{sum(len(nums[i]))} \le 10^5$
$1 \le nums[i][j] \le 10^5$

想法#

1
2
3

0,0 | 0,1 | 0,2 | 0,3
1,0 | 1,1 | 1,2 | 1,3
2,0 | 2,1 | 2,2 | 2,3

可以試著在紙上列出 nxm 的格子，觀察 index 的規律，可以發現在同個對角線上的數字，index $i+j$ 是一樣的，可以用這個方法來得知 nums[i][j] 是屬於哪一個對角線
接著可以發現對於同個對角線，index j 從小到大排正好是題目要求的順序，因此可以照此規律設計排序，把所有 i+j, i, j 綁在一起排序，先排 i+j (對角線），相同的 i+j 則排 j 。最後得到的即是題目要求的順序，轉成 nums[i][j] 輸出即可。

AC Code#

時間複雜度: $\mathcal{O}(n\log{n})$
空間複雜度: $\mathcal{O}(n)$

心得#

一開始也是沒想法，一直想要找 index 的規律加加減減的方法，後來劇透提示才寫出來QQ