LeetCode - 解题笔记 - 54 - Spiral MatrixSpiral Matrix

103 阅读 0 评论 68 点赞

我是靠谱客的博主无私棒棒糖，这篇文章主要介绍LeetCode - 解题笔记 - 54 - Spiral MatrixSpiral Matrix，现在分享给大家，希望可以做个参考。

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;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
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实现

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
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