leetcode54：螺旋矩阵

题目链接

leetcode

题目描述

给你一个 m 行 n 列的矩阵 matrix ，请按照顺时针螺旋顺序 ，返回矩阵中的所有元素。

C++ 代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
#include <iostream>
#include <vector>
using namespace std;

void printArray(const vector<int>& nums) {
    cout << "[";
    for (const int& num : nums) {
        cout << num << ",";
    }
    cout << "]" <<endl;
}

void printArray(const vector<vector<int>>& nums) {
    cout << "[";
    for (const vector<int>& num : nums) {
        cout << "[";
        for (const int& num2 : num) {
            cout << num2 << ",";
        }
        cout << "], ";
    }
    cout << "]" <<endl;
}

/*
    模拟
    初始位置是矩阵的左上角，初始方向是向右。
    当路径超出界限或者进入之前访问过的位置时，顺时针旋转并且进入下一个方向。

    时间复杂度：O(mn)
        其中 m 和 n 分别是输入矩阵的行数和列数。
        矩阵中的每个元素都要被访问一次。
    空间复杂度：O(mn)
        需要一个大小为 m*n 的矩阵，记录每个位置是否被访问过。
*/
class Solution_0 {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return {};

        int m = matrix.size(), n = matrix[0].size();
        vector<int> res(m * n);
        vector<vector<bool>> visited(m, vector<bool>(n));
        int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
        int x = 0, y = 0; // 起点 (x, y)
        int d = 1;        // 初始方向：向右
        for (int i = 0; i < m * n; i ++) {
            res[i] = matrix[x][y];
            visited[x][y] = true;
            int newX = x + dx[d], newY = y + dy[d];
            if (newX < 0 || newX >= m || newY < 0 || newY >= n || visited[newX][newY]) {
                d = (d + 1) % 4;
                newX = x + dx[d], newY = y + dy[d];
            }
            x = newX, y = newY;
        }

        return res;
    }
};

/*
    将矩阵看成若干层，首先输出最外层的元素，其次输出次外层的元素，直到输出最内层的元素。

    对于每层，从左上方开始以顺时针的顺序遍历所有元素。
    假设当前层的左上角位于 (top, left)，右下角位于 (bottom, right)，按照如下顺序遍历当前层的元素。
        1.从左到右遍历上侧元素，依次为 (top,left) 到 (top,right)。
        2.从上到下遍历右侧元素，依次为 (top + 1, right) 到 (bottom, right)。
        3.left < right 且 top < bottom，
            从右到左遍历下侧元素，依次为 (bottom, right − 1) 到 (bottom, left + 1)，
            从下到上遍历左侧元素，依次为 (bottom, left) 到 (top + 1, left)。
    遍历完当前层的元素之后，将 left 和 top 分别增加 1，将 right 和 bottom 分别减少 1，
    进入下一层继续遍历，直到遍历完所有元素为止。

    时间复杂度：O(mn)
        其中 m 和 n 分别是输入矩阵的行数和列数。
        矩阵中的每个元素都要被访问一次。
    空间复杂度：O(1)
        除了输出数组以外，空间复杂度是常数。
*/
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        if (matrix.size() == 0 || matrix[0].size() == 0) return {};

        int m = matrix.size(), n = matrix[0].size();
        vector<int> res;
        res.reserve(m * n);
        int left = 0, right = n - 1, top = 0, bottom = m - 1;
        while (left <= right && top <= bottom) {
            for (int col = left; col <= right; col ++) {
                res.push_back(matrix[top][col]);
            }
            for (int row = top + 1; row <= bottom; row ++) {
                res.push_back(matrix[row][right]);
            }
            if (left < right && top < bottom) {
                for (int col = right - 1; col > left; col --) {
                    res.push_back(matrix[bottom][col]);
                }
                for (int row = bottom; row > top; row --) {
                    res.push_back(matrix[row][left]);
                }
            }
            left ++, right --, top ++, bottom --;
        }

        return res;
    }
};

int main() {
    Solution solution;
    vector<vector<vector<int>>> nums = {
        {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}},
        {{5, 1, 9, 11}, {2, 4, 8, 10}, {13, 3, 6, 7}, {15, 14, 12, 16}}
    };

    for (auto& num : nums) {
        cout << "Input: ";
        printArray(num);
        vector<int> res = solution.spiralOrder(num);
        cout << "Output: ";
        printArray(res);
    }

    return 0;
}

Golang 代码

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
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
package main

import "fmt"

/*
	初始位置是矩阵的左上角，初始方向是向右。
	当路径超出界限或者进入之前访问过的位置时，顺时针旋转并且进入下一个方向。

   时间复杂度：O(mn)
       其中 m 和 n 分别是输入矩阵的行数和列数。
       矩阵中的每个元素都要被访问一次。
   空间复杂度：O(mn)
       需要一个大小为 m*n 的矩阵，记录每个位置是否被访问过。
*/
func spiralOrder_0(matrix [][]int) []int {
    m, n := len(matrix), len(matrix[0])
	if m == 0 || n == 0 {
		return []int{}
	}

	res := make([]int, m*n)
	visited := make([][]bool, m)
	for i := 0; i < m; i ++ {
		visited[i] = make([]bool, n)
	}
    
	dx := []int{-1, 0, 1, 0}
	dy := []int{0, 1, 0, -1}
	x, y := 0, 0 // 起点 (x, y)
	d := 1       // 初始方向：向右
	for i := 0; i < m*n; i ++ {
		res[i] = matrix[x][y]
		visited[x][y] = true
		newX, newY := x + dx[d], y + dy[d]
		if newX < 0 || newX >= m || newY < 0 || newY >= n || visited[newX][newY] {
			d = (d + 1) % 4
			newX, newY = x+dx[d], y+dy[d]
		}
		x, y = newX, newY
	}

	return res
}

/*
	1.初始化四个边界指针 top、bottom、left、right，分别表示矩阵的上、下、左、右边界。
	2.创建一个空的切片 result 用于存储螺旋顺序的元素。
	3.使用一个循环，按照螺旋顺序遍历矩阵：
		从左到右遍历上边界，将元素添加到 result 中。
		从上到下遍历右边界，将元素添加到 result 中。
		从右到左遍历下边界（如果下边界存在），将元素添加到 result 中。
		从下到上遍历左边界（如果左边界存在），将元素添加到 result 中。
	4.每次遍历完一个边界后，更新相应的边界指针，缩小矩阵的范围。
	5.重复步骤 3，直到所有元素都被遍历完。

   时间复杂度：O(mn)
       其中 m 和 n 分别是矩阵的行数和列数，
       遍历矩阵中的每个元素一次。
   空间复杂度：O(1)
       除了输出数组以外，空间复杂度是常数。
*/
func spiralOrder(matrix [][]int) []int {
	m, n := len(matrix), len(matrix[0])
	if m == 0 || n == 0 {
		return []int{}
	}

	res := make([]int, 0, m * n)
	top, bottom, left, right := 0, m - 1, 0, n - 1
	for top <= bottom && left <= right {
		// 从左到右遍历上边界
		for i := left; i <= right; i ++ {
			res = append(res, matrix[top][i])
		}
		top ++
		// 从上到下遍历右边界
		for i := top; i <= bottom; i ++ {
			res = append(res, matrix[i][right])
		}
		right --
		// 从右到左遍历下边界
		if top <= bottom {
			for i := right; i >= left; i -- {
				res = append(res, matrix[bottom][i])
			}
			bottom --
		}
		// 从下到上遍历左边界
		if left <= right {
			for i := bottom; i >= top; i -- {
				res = append(res, matrix[i][left])
			}
			left ++
		}
	}

	return res
}

func main() {
	// 测试用例
	testCases := []struct {
		matrix   [][]int
		expected []int
	}{
		{
			matrix: [][]int{
				{1,2,3},
				{4,5,6},
				{7,8,9},
			},
			expected: []int{1,2,3,6,9,8,7,4,5},
		},
		{
			matrix: [][]int{
				{1,2,3,4},
				{5,6,7,8},
				{9,10,11,12},
			},
			expected: []int{1,2,3,4,8,12,11,10,9,5,6,7},
		},
	}
	
	for i, tc := range testCases {
		result := spiralOrder(tc.matrix)
		fmt.Printf("Test Case %d, Input: matrix = %v\n", i+1, tc.matrix)
		resultStr := fmt.Sprintf("%v", result)
		expectedStr := fmt.Sprintf("%v", tc.expected)

		if resultStr == expectedStr {
			fmt.Printf("Test Case %d, Output: %v, PASS\n", i+1, resultStr)
		} else {
			fmt.Printf("Test Case %d, Output: %v, FAIL (Expected: %v)\n", i+1, resultStr, expectedStr)
		}
	}
}
#leetcode
leetcode54：螺旋矩阵
https://lcf163.github.io/2023/11/09/leetcode54：螺旋矩阵/
作者
乘风的小站
发布于
2023年11月9日
许可协议