原题地址:螺旋矩阵
给定一个包含 m x n 个元素的矩阵(m 行, n 列),请按照顺时针螺旋顺序,返回矩阵中的所有元素。
示例 1:
输入:
[
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
]
输出: [1,2,3,6,9,8,7,4,5]
示例 2:
输入:
[
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
]
输出: [1,2,3,4,8,12,11,10,9,5,6,7]
螺旋遍历
按照顺时针螺旋的顺序,分层遍历矩阵中的数据即可:
/**
* @param {number[][]} matrix
* @return {number[]}
*/
const spiralOrder1 = function(matrix) {
if (matrix.length === 0) {
return [];
}
let [m, n] = [matrix.length, matrix[0].length]; // 行数和列数
let result = []; // 结果集
// 螺旋前进时,每一次循环处理一圈,总圈数由行数和列数中较小的一个决定
for (let i = 0; i < Math.ceil(Math.min(m, n) / 2); i ++) {
// 处理一圈的上面一行
for (let j = i; j < n - i; j ++) {
result.push(matrix[i][j])
}
// 处理一圈的右边一列
for (let j = i + 1; j < m - i - 1; j ++) {
result.push(matrix[j][n - i - 1])
}
// 处理一圈的下面一行,如果已经与上面一行重叠则不用处理
if (m - i - 1 > i) {
for (let j = i; j < n - i; j ++) {
result.push(matrix[m - i - 1][n - j - 1])
}
}
// 处理一圈的左边一列,如果已经与右边一列重叠则不用处理
if (i < n - i - 1) {
for (let j = i + 1; j < m - i - 1; j ++) {
result.push(matrix[m - j - 1][i])
}
}
}
return result;
};
测试:
let start = new Date();
const test = spiralOrder1;
console.log(test([
[ 1, 2, 3 ],
[ 4, 5, 6 ],
[ 7, 8, 9 ]
])); // [1,2,3,6,9,8,7,4,5]
console.log(test([
[1, 2, 3, 4],
[5, 6, 7, 8],
[9,10,11,12]
])); // [1,2,3,4,8,12,11,10,9,5,6,7]
console.log(test([[7],[9],[6]])); // [7,9,6]
console.log(new Date().getTime() - start.getTime()); // 12
时间复杂度: 矩阵中所有元素都要被遍历一次,时间复杂度为$O(n)$,$n$为矩阵中的元素总数
空间复杂度: 需要一个数组来接收遍历的结果,数组的长度为矩阵中的元素总数,空间复杂度为$O(n)$
本文由 李海平 创作,采用 知识共享署名4.0
国际许可协议进行许可
本站文章除注明转载/出处外,均为本站原创或翻译,转载前请务必署名
最后编辑时间为: Aug 7,2019