Spiral Matrix

Solution 1

此题也是一个模拟题。利用分治的思想，对于整个矩阵，按照层次进行划分，这样每一层的数据读取顺序是一致的，这样就能够实现更好的代码复用。其中每一个“层”就是矩阵的一整个圈，读取顺序通过记录上下行和左右列的位置，并按照旋转方向进行读取。

• 时间复杂度：$O(N)$，其中$N$为输入矩阵的元素个数，算法中仅遍历所有元素一次
• 空间复杂度：$O(1)$，不考虑输出数据结构，仅维护常数个状态变量

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        auto ans = vector<int>();
        
        int top = 0, bottom = matrix.size() - 1;
        int left = 0, right = matrix[0].size() - 1;
        
        while (top <= bottom && left <= right) {
            // top-left to top-right
            for (int index = left; index <= right; ++index) { ans.emplace_back(matrix[top][index]); }
            // top-right to bottom-right
            for (int index = top + 1; index <= bottom; ++index) { ans.emplace_back(matrix[index][right]); }
            
            // 单数情形判定，只有一行或者一列
            if (top < bottom && left < right) {
                // bottom-right to bottom-left
                for (int index = right - 1; index >= left; --index) { ans.emplace_back(matrix[bottom][index]); }
                // bottom-left to top-left
                for (int index = bottom - 1; index > top; --index) { ans.emplace_back(matrix[index][left]); }
            }
                
            top++, bottom--;
            left++, right--;
        }
        
        return ans;
    }
};

Solution 2

Solution 1的Python实现

class Solution:
    def spiralOrder(self, matrix: List[List[int]]) -> List[int]:
        ans = list()
        
        top, left = 0, 0
        bottom, right = len(matrix) - 1, len(matrix[0]) - 1
        
        while top <= bottom and left <= right:
            for index in range(left, right + 1): ans.append(matrix[top][index])
            for index in range(top + 1, bottom + 1): ans.append(matrix[index][right])
                
            if top < bottom and left < right:
                for index in range(right - 1, left - 1, -1): ans.append(matrix[bottom][index])
                for index in range(bottom - 1, top, -1): ans.append(matrix[index][left])
                    
            top += 1
            bottom -= 1
            left += 1
            right -= 1
            
        return ans

最后

以上就是无私棒棒糖为你收集整理的LeetCode - 解题笔记 - 54 - Spiral MatrixSpiral Matrix的全部内容，希望文章能够帮你解决LeetCode - 解题笔记 - 54 - Spiral MatrixSpiral Matrix所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。