首页 > 试题广场 >

螺旋矩阵

[编程题]螺旋矩阵

热度指数：139185 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个m x n大小的矩阵（m行，n列），按螺旋的顺序返回矩阵中的所有元素。

数据范围： $0 \le n,m \le 10$ ，矩阵中任意元素都满足 $|val| \le 100$

要求：空间复杂度 $O(nm)$ ，时间复杂度 $O(nm)$

示例1

输入

[[1,2,3],[4,5,6],[7,8,9]]

输出

[1,2,3,6,9,8,7,4,5]

示例2

输入

[]

输出

[]

算法知识视频讲解

Python

和兔赛跑的龟

我也使用旋转生成新举证的思路解决，试图找到更加通用的旋转方法。结果没有使用zip函数直观。记录如下：

# @param matrix int整型二维数组
# @return int整型一维数组
#
class Solution:
    def spiralOrder(self, matrix):
        # write code here
        # 利用python中的zip函数
        # res = []
        # while matrix:
        #     res += matrix[0]
        #     matrix = list(zip(*matrix[1:]))[::-1]
        # return res
        rn = len(matrix)
        if rn == 0:
            res = []
        elif isinstance(matrix[0], int):
            res = matrix
        else:
            res = []
            while matrix:
                res.extend(matrix[0])
                matrix = self.rotate_matrix(matrix[1:])
                print(res)
        print("res:", res)
        return res

    def rotate_matrix(self, matrix):
        """
        矩阵旋转通用函数
        :param matrix:
        :return:
        """
        rn = len(matrix)
        if rn == 0:
            return matrix

        if isinstance(matrix[0], int):
            return matrix

        cn = len(matrix[0])
        print(rn, cn)
        r_matrix = [[0]*rn for i in range(cn)] #初始化逆时针旋转矩阵的大小
        for r in range(rn):
            for c in range(cn):
                # 逆时针旋转90度
                r_matrix[cn-c-1][r] = matrix[r][c]
                # 45度对角线翻转
                # r_matrix[cn-c-1][rn-r-1] = matrix[r][c]
                # 顺时针旋转90度
                # r_matrix[c][rn-r-1] = matrix[r][c]
        print(r_matrix)
        return r_matrix

编辑于 2021-05-12 19:47:40 回复(0)

Python

牛客314674748号

#
#
# @param matrix int整型二维数组
# @return int整型一维数组
#
class Solution:
def spiralOrder(self , matrix ):
# write code here
output = []
def rotateNegNinety(matrix):
if matrix == []:
return []
newMat = []
for j in range(len(matrix[0])):
curr = []
for i in range(len(matrix)):
curr.append(matrix[i][-j-1])
newMat.append(curr)
return newMat
def helper(matrix):
if matrix == []:
return
A = matrix.pop(0)
output.extend(A)
helper(rotateNegNinety(matrix))
helper(matrix)
return output

发表于 2021-04-17 20:20:03 回复(0)

Python

wengJJ

Python

#
# 
# @param matrix int整型二维数组 
# @return int整型一维数组
#
class Solution:
    def spiralOrder(self , matrix ):
        # write code here
#        测试用例里面有空矩阵
        if not matrix:
            return []
#        获取m行
        m = len(matrix)
#        获取n列
        n = len(matrix[0])
#        定义扫描方向
#        行的扫描方向 正向扫描、停止扫描、逆向扫描、停止扫描
        step_col = [1,0,-1,0]
#        列的扫描方向 停止扫描，正向扫描、停止扫描、逆向扫描
        step_raw = [0,1,0,-1]
#         扫描方向坐标
        step = 0
#         行列的起始坐标
        col_index=raw_index=0
        result = []
        for i in range(n*m):
            result.append(matrix[raw_index][col_index])
#             打上已扫描的标签-“v”
            matrix[raw_index][col_index] = 'v'
#             下一步的坐标
            tmp_col = col_index + step_col[step]
            tmp_raw = raw_index + step_raw[step]
#         如果未到达边际，继续扫描
            if 0<=tmp_col<n and 0<=tmp_raw<m and matrix[tmp_raw][tmp_col]!='v':
                col_index = tmp_col
                raw_index = tmp_raw
            else:
#         到达边际，通过改变扫描坐标来改变扫描方向
                step = (step+1)%4 
                col_index += step_col[step]
                raw_index += step_raw[step]
        return result

发表于 2021-04-13 13:06:28 回复(0)

Python

牛客104692173号

class Solution:
def spiralOrder(self , matrix ):
if not matrix:
return []
dx, dy = [0,1, 0,-1], [1, 0, -1, 0]
di = 0
length = len(matrix)*len(matrix[0])
m = len(matrix)
n = len(matrix[0])
res = [0]*length
x = y = 0
for i in range(length):
if x+dx[di]<m and y+dy[di]<n and matrix[x+dx[di]][y+dy[di]]!= None:
res[i] = matrix[x][y]
matrix[x][y] = None
x = x+dx[di]
y = y+dy[di]
else:
di = (di+1)%4
res[i] = matrix[x][y]
matrix[x][y] = None
x = x+dx[di]
y = y+dy[di]
return res

发表于 2021-03-17 18:25:01 回复(0)

Python

牛客378155865号

#
# 
# @param matrix int整型二维数组 
# @return int整型一维数组
#
class Solution:
    def spiralOrder(self , matrix ):
        # write code here
        if len(matrix) == 0:
            return []
        if len(matrix) == 1:
            return matrix[0]
        if len(matrix[0]) == 1:
            return list(map(list, zip(*matrix)))[::-1][0]
        res = []
        temp = matrix
        while len(temp) > 2:
            res = res + temp[0]
            temp = temp[1:]
            temp = list(map(list, zip(*temp)))[::-1] # roted
        res = res + temp[0] + list(reversed(temp[1]))
        return res

发表于 2021-03-14 16:19:05 回复(0)

Python

在下小6

python写的两种解法，思路是一样的，主要是避免重复存储的方法不同，欢迎指正！

"""
思路1：
1.从左到右：i=[left,right], matrix[top][i]
2.从上到下：i=[top+1,bottom], matrix[i][right]
3.从右到左：i=[right-1,left], matrix[bottom][i]
4.从下到上：i=[bottom-1,top+1], matrix[i][right]
注意：如何避免重复存储！采用边界条件来控制存储！
"""
class Solution:
    def spiralOrder(self , matrix ):
        res = []
        if len(matrix) == 0:
            return res
        top, left = 0, 0
        bottom = len(matrix) - 1
        right = len(matrix[0]) - 1
        while top <= bottom and left <= right:
            # 1.从左到右：i=[left,right], matrix[top][i]
            for i in range(left,right+1):
                res.append(matrix[top][i])

            # 2.从上到下：i=[top+1,bottom], matrix[i][right]
            for i in range(top+1,bottom+1):
                res.append(matrix[i][right])

            # 3.从右到左：i=[right-1,left], matrix[bottom][i]
            if top != bottom: 
                # 只剩一行时候，前面已经存储过，这里不再存储；
                for i in range(right-1,left-1,-1):
                    res.append(matrix[bottom][i])

            # 4.从下到上：i=[bottom-1,top+1], matrix[i][right]
            if left != right:
                # 只剩一列时候，前面已经存储过，这里不再存储；
                for i in range(bottom-1,top,-1):
                    res.append(matrix[i][left])

            top += 1
            right -= 1
            bottom -= 1
            left += 1
        return res

"""
思路2：
1.从左到右：i=[left,right], matrix[top][i]
2.从上到下：i=[top+1,bottom], matrix[i][right]
3.从右到左：i=[right-1,left], matrix[bottom][i]
4.从下到上：i=[bottom-1,top+1], matrix[i][right]
注意：如何避免重复存储！计算一共存储了多少个元素。
"""
class Solution:
    def spiralOrder(self , matrix ):
        res = []
        if len(matrix) == 0:
            return res
        top, left = 0, 0
        bottom = len(matrix) - 1
        right = len(matrix[0]) - 1
        num = (bottom+1) * (right+1)
        while num > 0:
            # 判断全部元素是否存储完毕
            # 1.从左到右：i=[left,right], matrix[top][i]
            for i in range(left,right+1):
                if num > 0:
                    res.append(matrix[top][i])
                    num -= 1

            # 2.从上到下：i=[top+1,bottom], matrix[i][right]
            for i in range(top+1,bottom+1):
                if num > 0:
                    res.append(matrix[i][right])
                    num -= 1

            # 3.从右到左：i=[right-1,left], matrix[bottom][i]
            for i in range(right-1,left-1,-1):
                if num > 0:
                    res.append(matrix[bottom][i])
                    num -= 1

            # 4.从下到上：i=[bottom-1,top+1], matrix[i][right]
            for i in range(bottom-1,top,-1):
                if num > 0:
                    res.append(matrix[i][left])
                    num -= 1

            top += 1
            right -= 1
            bottom -= 1
            left += 1
        return res

编辑于 2021-02-13 20:15:36 回复(0)

Python

黄沙遮天

这道题使用的方法是一圈圈的读矩阵中的元素，我们设定对角线上的元素作为每个圈的起始元素，接下来就是判断每圈读的时候都做了哪些操作。首先是读取最上面一行，然后是读取最后一列（这要求行数大于起始），接着是读取最后一行（这个要求行数大于起始，并且列数也要大于起始），最后是读取第一列（这个要求是行数大于起始+1，列数大于起始）

#
#
# @param matrix int整型二维数组
# @return int整型一维数组
#
class Solution:
    def printMatrixCircle(self,matrix,rows,cols,start,totallist):
        endx=cols-start
        endy=rows-start
        for i in range(start,endx+1):
            totallist.append(matrix[start][i])
        if endy>start:
            for i in range(start+1,endy+1):
                totallist.append(matrix[i][endx])
        if(start<endx and start<endy):
            for i in range(endx-1,start-1,-1):
                totallist.append(matrix[endy][i])
        if(start<endx and start<endy-1):
            for i in range(endy-1,start,-1):
                totallist.append(matrix[i][start])
    def spiralOrder(self , matrix ):
        # write code here
        if matrix==[]:
            return []
        rows=len(matrix)
        cols=len(matrix[0])
        if rows<=0&nbs***bsp;cols<=0:
            return []
        if rows==1:
            temlist=[i for i in matrix[0]]
            return temlist
        start=0
        totallist=[]
        while(cols>start*2 and rows>start*2):
            self.printMatrixCircle(matrix,rows-1,cols-1,start,totallist)
            start+=1
        return totallist

发表于 2020-09-21 16:41:16 回复(0)