1424. Diagonal Traverse II
給你一個二維整數陣列
回傳對角線排序的陣列
Input: nums = [[1,2,3],[4,5,6],[7,8,9]]
Output: [1,4,2,7,5,3,8,6,9]
https://assets.leetcode.com/uploads/2020/04/08/sample_1_1784.png
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]
https://assets.leetcode.com/uploads/2020/04/08/sample_2_1784.png
Intuition:
一開始我是想用兩個變數startRow跟index去跑兩層迴圈
一直跑到沒有新元素被加進陣列為止
結果這個解法超慢
時間複雜度是O(n^2)
Approach:
後來看別人解法
(最近都在抄答案 我好爛)
他們用一個待處裡的序列
從起點[0,0]開始
每次都把處理中元素下面跟右邊的元素加到待處理陣列
這樣就不會一直計算陣列外無意義的資料
TS Code:
function findDiagonalOrder (nums: number[][]): number[] {
const queue: [number, number][] = [[0, 0]]
const result: number[] = []
while (queue.length > 0) {
const [i, j] = queue.shift()
result.push(nums[i][j])
if (j === 0 && nums[i + 1]?.[j] != null) queue.push([i + 1, j])
if (nums[i]?.[j + 1] != null) queue.push([i, j + 1])
}
return result
}