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
}