LeetCode 54. 螺旋矩阵

作者:Choi Yang

更新于:7 个月前

字数统计:962 字

阅读时长:4 分钟

题目描述

给定一个包含 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]

来源：力扣（LeetCode）链接：https://leetcode-cn.com/problems/spiral-matrix 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题思路

和 上一期 螺旋矩阵差不多，这个是让我么输出，而上次是让我们构造，还是按照螺旋矩阵模拟即可，先从左到右，在从上到下，再从右到左，再从下到上。

不过这里的矩阵行和列不相同了，可能会出现不成环的情况，那么最后会留一列或一行出来，这里借用大佬一张图：

然后我们需要提前跳出去一下，就是避免重复计算，总数够了直接跳出去。注意下面代码 break。只能放在那里，因为遍历顺序，如果最后留下一行的话，需要从左到右遍历，此时 top > bottom 。如果最后留下一列的话，需要从上到下遍历，此时 left > right。

javascript

/**
 * @param {number[][]} matrix
 * @return {number[]}
 */
var spiralOrder = function (matrix) {
  if (!matrix.length) return [];
  let n = matrix.length;
  let m = matrix[0].length;
  let total = n * m;
  let top = 0,
    bottom = n - 1;
  let left = 0,
    right = m - 1;
  let res = [];
  while (res.length < total) {
    for (let i = left; i <= right; i++) res.push(matrix[top][i]); // 从左到右
    top++;
    for (let i = top; i <= bottom; i++) res.push(matrix[i][right]); // 从上到下
    right--;
    /* 因为n 和 m 不相同的时候，最后可能会留一列或一行，避免重复计算，总数够了直接跳出去 */
    if (res.length === total) break;
    for (let i = right; i >= left; i--) res.push(matrix[bottom][i]); // 从右到左
    bottom--;
    for (let i = bottom; i >= top; i--) res.push(matrix[i][left]); // 从下到上
    left++;
  }
  return res;
};

cpp

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.empty()) return {};
        int n = matrix.size();
        int m = matrix[0].size();
        int total = n * m;
        int top = 0, bottom = n - 1;
        int left = 0, right = m - 1;
        vector<int> res;
        while (res.size() < total) {
            for (int i = left; i <= right; i++) res.push_back(matrix[top][i]); // 从左到右
            top++;
            for (int i = top; i <= bottom; i++) res.push_back(matrix[i][right]); // 从上到下
            right--;
            /* 因为n 和 m 不相同的时候，最后可能会留一列或一行，避免重复计算，总数够了直接跳出去 */
            if (res.size() == total) break;
            for (int i = right; i >= left; i--) res.push_back(matrix[bottom][i]); // 从右到左
            bottom--;
            for (int i = bottom; i >= top; i--) res.push_back(matrix[i][left]); // 从下到上
            left++;
        }
        return res;
    }
};

java

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        if (matrix.length == 0) return new ArrayList<>();
        int n = matrix.length;
        int m = matrix[0].length;
        int total = n * m;
        int top = 0, bottom = n - 1;
        int left = 0, right = m - 1;
        List<Integer> res = new ArrayList<>();
        while (res.size() < total) {
            for (int i = left; i <= right; i++) res.add(matrix[top][i]); // 从左到右
            top++;
            for (int i = top; i <= bottom; i++) res.add(matrix[i][right]); // 从上到下
            right--;
            /* 因为n 和 m 不相同的时候，最后可能会留一列或一行，避免重复计算，总数够了直接跳出去 */
            if (res.size() == total) break;
            for (int i = right; i >= left; i--) res.add(matrix[bottom][i]); // 从右到左
            bottom--;
            for (int i = bottom; i >= top; i--) res.add(matrix[i][left]); // 从下到上
            left++;
        }
        return res;
    }
}

python

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        if not matrix: return []
        n = len(matrix)
        m = len(matrix[0])
        total = n * m
        top = 0
        bottom = n - 1
        left = 0
        right = m - 1
        res = []
        while len(res) < total:
            for i in range(left, right + 1): res.append(matrix[top][i]) # 从左到右
            top += 1
            for i in range(top, bottom + 1): res.append(matrix[i][right]) # 从上到下
            right -= 1
            if len(res) == total: break
            for i in range(right, left - 1, -1): res.append(matrix[bottom][i]) # 从右到左
            bottom -= 1
            for i in range(bottom, top - 1, -1): res.append(matrix[i][left]) # 从下到上
            left += 1
        return res

学如逆水行舟，不进则退

Contributors

Choi Yang