返回

[Leetcode]54. Spiral Matrix(C++)

题目描述

题目链接:54. Spiral Matrix

Given an m x n matrix, return all elements of the matrix in spiral order.

例子

例子 1

Input: matrix = [[1,2,3],[4,5,6],[7,8,9]] Output: [1,2,3,6,9,8,7,4,5]

例子 2

Input: matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]] Output: [1,2,3,4,8,12,11,10,9,5,6,7]

Constraints

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 10
  • -100 <= matrix[i][j] <= 100

解题思路

沿螺旋方向遍历矩阵,可以从外层开始遍历,每次遍历一圈,然后层层深入即可。在遍历一圈要注意各个方向的起点和边界。

代码如下:

#include <vector>

class Solution {
public:
    std::vector<int> spiralOrder(std::vector<std::vector<int>>& matrix) {
        std::vector<int> result;
        int m = matrix.size();
        int n = matrix[0].size();
        int row1 = 0;
        int row2 = m - 1;
        int col1 = 0;
        int col2 = n - 1;
        while (row1 <= row2 && col1 <= col2) {
            for (int c = col1; c <= col2; ++c) {
                result.push_back(matrix[row1][c]);
            }
            for (int r = row1 + 1; r <= row2; ++r) {
                result.push_back(matrix[r][col2]);
            }
            if (row1 < row2 && col1 < col2) {
                for (int c = col2 - 1; c > col1; --c) {
                    result.push_back(matrix[row2][c]);
                }
                for (int r = row2; r > row1; --r) {
                    result.push_back(matrix[r][col1]);
                }
            }
            row1++;
            row2--;
            col1++;
            col2--;
        }

        return result;
    }
};
  • 时间复杂度: O(n)
  • 空间复杂度: O(1)

GitHub 代码同步地址: 54.SpiralMatrix.cpp

其他题目: GitHub: Leetcode-C++-Solution 博客: Leetcode-Solutions

Built with Hugo
Theme Stack designed by Jimmy