題目敘述
題目會給我們一個不規則排列的二維陣列，要求我們列出從起點出發，走次對角線方向，由左下到右上逐層拜訪的路徑。
測試範例
Example 1:
Input: nums = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,4,2,7,5,3,8,6,9]
Example 2:
Input: nums = [[1,2,3,4,5],[6,7],[8],[9,10,11],[12,13,14,15,16]]
Output: [1,6,2,8,7,3,9,4,12,10,5,13,11,14,15,16]
約束條件
Constraints:
1 <= nums.length <= 10^51 <= nums[i].length <= 10^51 <= sum(nums[i].length) <= 10^51 <= nums[i][j] <= 10^5
演算法
除了傳統的次對角線方向總合當作鍵值的字典演算法之外，還有一個高效率的BFS演算法。
我們可以這樣想，把左上角(0, 0)這個座標當作起點。依循BFS的原則，往右下角擴散。
假設當下拜訪到的座標為(x, y)
當現在位在最左邊的column時，把下方的鄰居(x, y+1)推入BFS queue。
當現在不在最右邊的column時，把右邊的鄰居(x+1, y)推入BFS queue。
接著，把拜訪到的元素值記錄下來，就是最終答案。
從起點 左上角的1出發
拜訪1 的時侯，加入鄰居 4, 2
拜訪4 的時侯，加入鄰居 7, 5
拜訪2 的時侯，加入鄰居 3
拜訪7 的時侯，加入鄰居 8
拜訪5 的時侯，加入鄰居 6
拜訪3 已經抵達最右邊的column
拜訪8 的時侯，加入鄰居 9
拜訪6 已經抵達最右邊的column
拜訪9 已經抵達最右邊的column
最後，整個次對角線的拜訪路徑就是
1, 4, 2, 7, 5, 3, 8, 6, 9
程式碼
class Solution:
def findDiagonalOrder(self, nums: List[List[int]]) -> List[int]:
# Height of input 2D array
H = len(nums)
# 2D (x, y) coordination of each grid
traversal_q = deque( [(0, 0)] )
# record of traversal path
record = []
# Launch BFS traversal from staring point (0, 0)
while traversal_q:
## Add current grid to record of traversal path
x, y = traversal_q.popleft()
record.append( nums[y][x] )
## Add neighbor below on the leftmost column
if x == 0 and ( (y + 1) < H ):
traversal_q.append( (x, y+1) )
## Add neighbor on right hand side
# Get width of current row dynamically
cur_width = len( nums[y] )
if x + 1 < cur_width:
traversal_q.append( (x+1, y) )
return record
關鍵知識點
本題目切忌先入為主，把題目當成方陣或矩陣。
這題的輸入其實是不規則的二維陣列。
可以想到BFS演算法，把矩陣的每個格子點視為一個節點，相鄰的節點有一條邊相連。
我們可以這樣想，把左上角(0, 0)這個座標當作起點。依循BFS廣度優先的原則，往右下角擴散。
最後整個BFS拜訪順序的軌跡，就是答案。
Reference:
[1] Python O(HW) on BFS and neighbor growing [w/ Visualization] - Diagonal Traverse II - LeetCode
