螺旋矩阵__牛客网

实在学不动了

转圈圈，利用四个整数来给接下来要转的圈的上下左右边界做标记就可以了

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int>>& matrix) {
        vector<int> answer;
        if(matrix.size()==0) return answer; 
        int top=0,bottom=matrix.size()-1,left=0,right=matrix[0].size()-1;
        while((bottom-top)>=0&&(right-left)>=0) {
            if((bottom-top)>0&&(right-left)>0) {  //还有多行多列
                for(int i=left;i<right;i++) answer.push_back(matrix[top][i]);   //向右压入
                for(int i=top;i<bottom;i++) answer.push_back(matrix[i][right]);  //向下压入
                for(int i=right;i>left;i--) answer.push_back(matrix[bottom][i]);  //向左压入
                for(int i=bottom;i>top;i--) answer.push_back(matrix[i][left]);//向上压入      
            }
            else if((right-left)>0&&(bottom-top)==0) { //只剩一行
                for(int i=left;i<=right;i++) answer.push_back(matrix[top][i]);   //向右压入，只剩一行时要注意要取到right
            }
            else if((right-left)==0&&(bottom-top)>0) {  //只剩一列
                for(int i=top;i<=bottom;i++) answer.push_back(matrix[i][right]);  //向下压入，只剩一列时要注意要取到bottom，因为不会再有向左向右那些操作了
            }
            else if((right-left)==0&&(bottom-top)==0) { //只剩一个
                answer.push_back(matrix[top][right]);
                break;
            }
            bottom--;top++;left++;right--;
        }
        return answer;
    }
};

发表于 2020-06-19 14:36:03 回复(0)

dahaiyidi

//shijian:m*n
//kongjian:1
import java.util.*;
public class Solution {
public ArrayList<Integer> spiralOrder(int[][] matrix) {
ArrayList<Integer> res=new ArrayList<Integer>();
if(matrix==null || matrix.length==0 || matrix[0].length==0) return res;
int m=matrix.length;
int n=matrix[0].length;
for(int i=0;i<=Math.min(m-1,n-1)/2;i++)////////////////////////////////////////////
{
for(int k=0+i;k<=n-1-i;k++)
res.add(matrix[0+i][k]);
for(int k=1+i;k<=m-1-i;k++)
res.add(matrix[k][n-1-i]);
for(int k=n-2-i;(m-1-i)>i && k>=0+i;k--)//////////////////////////
res.add(matrix[m-1-i][k]);
for(int k=m-2-i;i<n-1-i && k>=1+i;k--)//////////////////////////
res.add(matrix[k][0+i]);
}
return res;
}
}

发表于 2018-05-20 20:33:54 回复(0)

Python 3

牛客371766835号

class Solution:
def spiralOrder(self , matrix):



#行
m = len(matrix)
if( m == 0 ):
return []
#列
n = len(matrix[0])
if (n == 0):
return []

mapbook = [[1 for i in range(n)] for j in range(m)]

#print(mapbook)
#print("m:",m)
#print("n:",n)

r = 0
c = -1
res = []
for i in range(m*n):
#右
while( c < n-1 and mapbook[r][c+1]==1 ):
c = c + 1
res.append(matrix[r][c])
mapbook[r][c] = 0
#print("右")
#print(mapbook)
#下
while( r < m -1 and mapbook[r+1][c] == 1 ):
r = r + 1
res.append(matrix[r][c])
mapbook[r][c] = 0
#print("下")
#左
while(c > 0 and mapbook[r][c-1] == 1):
c = c - 1
res.append(matrix[r][c])
mapbook[r][c] = 0
#print("左")
#上
while(r > 0 and mapbook[r -1 ][c] == 1):
r = r -1
res.append(matrix[r][c])
mapbook[r][c] = 0
#print("上")
return res

发表于 2022-01-23 02:38:57 回复(0)

C++

牛客655463886

设置4个边界，先向右，然后向下，向左，向上，然后更新4个边界，在走一圈，以此往复

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> >& matrix) 
    {
        vector<int>a;
        int i=0, j=-1,flag=0;
        int left = 0,right = matrix[0].size(),top = 0, bottom = matrix.size();
        if (matrix.empty()) return a;
        while (left < right && bottom > top)
        {
            while (j < right-1)
            {
                j++;
                a.push_back(matrix[i][j]);
                flag=1;
            }
            while (i < bottom-1 && flag>0)
            {
                i++;
                a.push_back(matrix[i][j]);
                flag=2;
            }
            while (j > left && flag>1)
            {   
                j--;
                a.push_back(matrix[i][j]);
                flag=3;
            }
            while (i > top+1 && flag>2)
            {
                i--;
                a.push_back(matrix[i][j]);
            }
            flag=0;
            left++, right--, top++, bottom--;
        }
        return a;
    }
};

发表于 2021-10-01 16:58:17 回复(0)

Python3

牛客343459580号

难点在于分析每个角落转向的规律，画个5*3图就明了了，i，j，i为行，j为列，m,n为行数和列数还要考虑空的情况（坑）

左上：原本是up走向，且要有i-j = 1，顺时针转90度，变成right

右上：原本是right走向，且要有i+j = n-1，顺时针转90度，变成right

右下：原本是down走向，且要有m-i = n-j，实际上就是下标【-1，-1】，【-2，-2】这种,顺时针转90度，变成right

左下：原本是left走线和，且要有i+j = m-1，顺时针转90度，变成right

class Solution:
    def spiralOrder(self,matrix):
        # write code here
        num = 1#记录走过的位置的数量
        i = 0
        j = 0
        way = 1#1right,2down,3left,4up,用来标志此时车车往哪个方向走
        m = len(matrix)
        if(m == 0):
            n = 0
        else:
            n = len(matrix[0])
        save = []
        while(num<=m*n):
            save.append(matrix[i][j])
            if(way == 1 and (i+j == n-1)):#right to down
                way = 2
            elif(way == 2 and m-i == n-j):#down to left
                way = 3
            elif(way == 3 and i+j == m-1):#left to up
                way = 4
            elif(way == 4 and i-j == 1):#up to right
                way = 1

            if(way == 1):
                j += 1
            elif(way == 2):
                i += 1
            elif(way == 3):
                j -= 1
            elif(way == 4):
                i -= 1
            num += 1
        return save

发表于 2021-09-02 23:05:41 回复(0)

C++

我跟你说

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        if (matrix.empty() || matrix[0].empty()) return {};
        int n = matrix.size(), m = matrix[0].size();
        vector<int> res;
        int l = 0, r = m - 1, u = 0, d = n - 1;
        while (res.size() < m * n) {
            if (u <= d)for (int i = l; i <= r; i++) {res.emplace_back(matrix[u][i]);}
            u++;
            if (l <= r)for (int i = u; i <= d; i++) {res.emplace_back(matrix[i][r]);}
            r--;
            if (u <= d)for (int i = r; i >= l; i--) {res.emplace_back(matrix[d][i]);}
            d--;
            if (l <= r)for (int i = d; i >= u; i--) {res.emplace_back(matrix[i][l]);}
            l++;
        
        }
        return res;
    }
};

美观

发表于 2021-07-29 15:40:57 回复(0)

勇敢牛牛，不怕困难！

/**
 * 
 * @param matrix int整型二维数组 
 * @param matrixRowLen int matrix数组行数
 * @param matrixColLen int* matrix数组列数
 * @return int整型一维数组
 * @return int* returnSize 返回数组行数
 */
int* spiralOrder(int** matrix, int matrixRowLen, int* matrixColLen, int* returnSize) {
  const int m = matrixRowLen, n = *matrixColLen;
  
  int top = 0, bottom = m - 1,
      left = 0, right = n - 1,
      x, y, dir = 0;
  
  int* ans = (int*) malloc(m * n * sizeof(int));
  *returnSize = 0;
  
  while (left <= right && top <= bottom) {
    switch (dir) {
      case 0:
        for (x = left; x <= right; ++x)
          *(ans + (*returnSize)++) = matrix[top][x];
        ++top;
        break;
      case 1:
        for (y = top; y <= bottom; ++y)
          *(ans + (*returnSize)++) = matrix[y][right];
        --right;
        break;
      case 2:
        for (x = right; x >= left; --x)
          *(ans + (*returnSize)++) = matrix[bottom][x];
        --bottom;
        break;
      case 3:
        for (y = bottom; y >= top; --y)
          *(ans + (*returnSize)++) = matrix[y][left];
        ++left;
        break;
      default:
        puts("dir 有问题耶！");
        break;
    }
    dir = (dir + 1) % 4;
  }
  
  return ans;
}

发表于 2021-07-07 07:37:02 回复(0)

Java

Mono_Chrome

import java.util.ArrayList;

public class Solution {

    public ArrayList<Integer> list = new ArrayList<>();

    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return list;
        }
        int tR = 0;
        int tC = 0;
        int dR = matrix.length - 1;
        int dC = matrix[0].length - 1;
        while (tR <= dR && tC <= dC) {
            printEdge(matrix, tR++, tC++, dR--, dC--);
        }
        return list;
    }

    public void printEdge(int[][] matrix, int tR, int tC, int dR, int dC) {
        if (tR == dR) {
            for (int i = tC; i <= dC; i++) {
                list.add(matrix[tR][i]);
            }
        } else if (tC == dC) {
            for (int i = tR; i <= dR; i++) {
                list.add(matrix[i][tC]);
            }
        } else {
            int i = tR;
            int j = tC;
            while (j < dC) {
                list.add(matrix[tR][j++]);
            }
            while (i < dR) {
                list.add(matrix[i++][dC]);
            }
            while (j > tC) {
                list.add(matrix[dR][j--]);
            }
            while (i > tR) {
                list.add(matrix[i--][tC]);
            }
        }
    }
}

发表于 2021-05-26 19:53:47 回复(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)

肥猿

解题思路：按顺时针的顺序，调整方向，一直沿某一个方向走，添加元素，终止条件为，遍历的行数，上大于下，或者遍历的列数，左大于右

import java.util.*;

public class Solution {
public ArrayList<Integer> spiralOrder(int[][] matrix) {
ArrayList<Integer> res = new ArrayList<Integer>();

if (matrix.length == 0) {
return res;
}

int rowBegin = 0;
int rowEnd = matrix.length-1;
int colBegin = 0;
int colEnd = matrix[0].length - 1;

while (rowBegin <= rowEnd && colBegin <= colEnd) {
// Traverse Right
for (int j = colBegin; j <= colEnd; j ++) {
res.add(matrix[rowBegin][j]);
}
rowBegin++;
// Traverse Down
for (int j = rowBegin; j <= rowEnd; j ++) {
res.add(matrix[j][colEnd]);
}
colEnd--;
if (rowBegin <= rowEnd) {
// Traverse Left
for (int j = colEnd; j >= colBegin; j --) {
res.add(matrix[rowEnd][j]);
}
}
rowEnd--;
if (colBegin <= colEnd) {
// Traverse Up
for (int j = rowEnd; j >= rowBegin; j --) {
res.add(matrix[j][colBegin]);
}
}
colBegin ++;
}
return res;
}
}

发表于 2021-03-13 15:24:43 回复(0)

C/C++

Mysf

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        if(matrix.size() == 0)
            return {};
        
        int m = matrix.size(), n = matrix[0].size();
        vector<int> ans;
        
        int left_row = 0, left_col = 0, right_row = m - 1, right_col = n - 1; //左上角和右下角坐标
        while (left_row <= right_row && left_col <= right_col) {
            for (int i = left_row; i <= right_col; i++)     //走到最右边
                ans.push_back(matrix[left_row][i]);
            
            for (int i = left_row + 1; i <= right_row; i++)  //走到最下边
                ans.push_back(matrix[i][right_col]);
            
            for (int i = right_col - 1; i >= left_col && left_row != right_row; i--)  //往左走到底，left_row != right_row 只有一行时不用走回来，前面已经走了
                ans.push_back(matrix[right_row][i]);
            
            for (int i = right_row - 1; i >= left_row + 1 && left_col != right_col; i--) //往上走，left_col != right_col 只有一列时不用走回来，前面已经走了
                ans.push_back(matrix[i][left_col]);
            left_col++;
            left_row++;
            right_col--;
            right_row--;
        }
        return ans;
    }
};

发表于 2021-02-03 14:38:24 回复(0)

Java

傲娇猫

螺旋打印主要需要打印四个边，上边是从左向右正序打印，右边是从上到下正序打印，下边是从右向左倒叙打印，左边是自下向上打印。

import java.util.*;
public class Solution {
    public ArrayList<Integer> spiralOrder(int[][] array) {
             ArrayList<Integer> list = new ArrayList<>();
        // 如果二维数组为空，返回空的list
        if(array.length == 0){
            return list;
        }
        int top = 0;
        int right = array[0].length -1;
        int bottom = array.length - 1;
        int left = 0;

        while (true){
            // top 上边是正序打印
            for (int i = left; i <= right; i++) {
                list.add(array[top][i]);
            }
            top++;
            if(left>right || top>bottom){
                break;
            }
            // 打印右边，从上之下正序打印
            for (int i = top; i <= bottom; i++) {
                list.add(array[i][right]);
            }
            right--;
            if(left>right || top>bottom){
                break;
            }
            // 打印最低边，从右向左倒叙打印
            for (int i = right; i >=left; i--) {
                list.add(array[bottom][i]);
            }
            bottom --;
            if(left>right || top>bottom){
                break;
            }
            // 最左边从下自上打印
            for (int i = bottom; i >=top ; i--) {
                list.add(array[i][left]);
            }
            left++;
            if(left>right || top>bottom){
                break;
            }
        }
        return list;
    }
}

发表于 2020-11-25 18:34:17 回复(0)

继续加油～

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &vec) {
        vector<int> res;
        int row_len = vec.size();
        if(!row_len) return res;
        int col_len = vec[0].size();
        if(!col_len) return res;
        int cou = 0;
        int l = 0, r = col_len-1, u = 0, d = row_len-1;
        int i;
        while(true)
        {
            for(i=l;i<=r;++i,++cou) res.push_back(vec[u][i]);
            if(cou>=row_len*col_len) break;
            ++u;
            for(i=u;i<=d;++i,++cou) res.push_back(vec[i][r]);
            if(cou>=row_len*col_len) break;
            --r;
            for(i=r;i>=l;--i,++cou) res.push_back(vec[d][i]);
            if(cou>=row_len*col_len) break;
            --d;
            for(i=d;i>=u;--i,++cou) res.push_back(vec[i][l]);
            if(cou>=row_len*col_len) break;
            ++l;
        }
        return res;
    }
};

发表于 2019-04-30 13:05:53 回复(0)

zbbsyx

class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> res;
        int rows = matrix.size();
        if(rows <= 0) return res;
        int cols = matrix[0].size();
        int elements = rows * cols;
        bool direction = 0;
        int up = 0, left = 0, down = rows - 1, right = cols - 1;
        while(res.size() < elements){
            direction ^= 1;
            if(direction){
                for(int i = left; i <= right; i++)
                    res.push_back(matrix[up][i]);
                up ++ ;
                for(int i = up; i <= down; i++)
                    res.push_back(matrix[i][right]);
                right --;
            }
            else{
                for(int i = right; i >= left; i--)
                    res.push_back(matrix[down][i]);
                down -- ;
                for(int i = down; i >= up; i--)
                    res.push_back(matrix[i][left]);
                left ++;
            }
        }
        return res;
    }
};

发表于 2019-04-21 09:29:17 回复(0)

丶沉梦昂志

 import java.util.*;

public class Solution {
    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> res = new ArrayList<>();
        if (matrix.length == 0) return res;
        int m = matrix.length, n = matrix[0].length;
        int lvl = (Math.min(m, n) + 1) / 2;        // 计算圈数
        for (int i = 0; i < lvl; i++) {
            // 计算相对应的该圈最后一行
            int lastRow = m - i - 1;
            // 计算相对应的该圈最后一列
            int lastCol = n - i - 1;
            // 如果该圈第一行就是最后一行，说明只剩下一行
            if (i == lastRow) {
                for (int j = i; j <= lastCol; j++) {
                    res.add(matrix[i][j]);
                }
                // 如果该圈第一列就是最后一列，说明只剩下一列
            } else if (i == lastCol) {
                for (int j = i; j <= lastRow; j++) {
                    res.add(matrix[j][i]);
                }
            } else {
                // 第一行
                for (int j = i; j < lastCol; j++) {
                    res.add(matrix[i][j]);
                }
                // 最后一列
                for (int j = i; j < lastRow; j++) {
                    res.add(matrix[j][lastCol]);
                }
                // 最后一行
                for (int j = lastCol; j > i; j--) {
                    res.add(matrix[lastRow][j]);
                }
                // 第一列
                for (int j = lastRow; j > i; j--) {
                    res.add(matrix[j][i]);
                }
            }
        }
        return res;
    }
}

发表于 2017-11-22 16:00:07 回复(0)

页川先生

 void edge(vector<vector<int>> &matrix,int ax,int ay,int bx,int by,vector<int> &res){
        if(ax==bx){
            while(ay<=by){
                res.push_back(matrix[ax][ay++]);
            }
        }
        else if(ay==by){
            while(ax<=bx){
                res.push_back(matrix[ax++][ay]);
            }
        }
        else{
            int j=ay;
            int i=ax;
            while(j!=by){
                res.push_back(matrix[ax][j++]);
            }
            while(i!=bx){
                res.push_back(matrix[i++][by]);
            }
            while(j!=ay){
                res.push_back(matrix[bx][j--]);
            }
            while(i!=ax){
                res.push_back(matrix[i--][ay]);
            }
        }
    }
    
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> res;
        if(matrix.size()==0)
            return res;
        int rows=matrix.size();
        int cols=matrix[0].size();
        int TLx=0;
        int TLy=0;
        int BRx=rows-1;
        int BRy=cols-1;
        while(TLx<=BRx&&TLy<=BRy){
            edge(matrix,TLx++,TLy++,BRx--,BRy--,res);
        }
        return res;
    }

发表于 2017-11-06 17:04:44 回复(0)

Java

Holiday_12138

import java.util.*;
public class Solution {
    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        if(matrix == null || matrix.length < 1 || matrix[0].length < 1)
            return new ArrayList<Integer>();
        int top = 0;
        int bottom = matrix.length-1;
        int left = 0;
        int right = matrix[0].length-1;
        ArrayList<Integer> res = new ArrayList<Integer>();
        while(top <= bottom && left <= right) {
            for(int i=left; i <= right && top <= bottom; i++)
                res.add(matrix[top][i]);
            top++;
            for(int i=top; i <= bottom && left <= right; i++)
                res.add(matrix[i][right]);
            right--;
            for(int i=right; i >= left && top <= bottom; i--)
                res.add(matrix[bottom][i]);
            bottom--;
            for(int i=bottom; i >= top && left <= right; i--)
                res.add(matrix[i][left]);
            left++;
        }
        return res;
    }
}

发表于 2017-06-19 16:46:25 回复(0)

后劲好大

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> list = new ArrayList<>();
        if(matrix == null || matrix.length <= 0 || matrix[0].length <= 0)
        	return list;
        
        int m = matrix.length;
        int n = matrix[0].length;
     // 计算需要循环的次数
        int time = (Math.min(m, n) + 1) / 2;
        int x = 0, y = 0;
        for(int i = 0; i < time; i++){
        	x = i;
        	y = i;
        	int startx = x;
        	int starty = y;
        	int endx = m - x - 1;
        	int endy = n - y - 1;
        	
        	// 只有一列或者一行
        	if(m == 1 || n == 1){
        		if(m == 1){
        			for(int j = 0; j < n; j++)
        				list.add(matrix[0][j]);
        		}
        		else if(n == 1){
        			for(int j = 0; j < m; j++)
        				list.add(matrix[j][0]);
				}
        		continue;
        	}
        	
        	if(x == endx && y == endy){
        		list.add(matrix[x][y]);
        		continue;
        	}
        	
        	while(y < endy){
        		list.add(matrix[x][y]);
        		y++;
        	}
        	while(x < endx){      		
        		list.add(matrix[x][y]);
        		x++;
        	}
        	while(y > starty){
        		list.add(matrix[x][y]);
        		y--;
        	}
        	while(x > startx){
        		list.add(matrix[x][y]);
        		x--;
        	}
        }
        return list;
    }
}

发表于 2017-05-22 21:40:06 回复(0)

001ya～

思路：一次循环就对一个方框进行操作。操作完后，方框大小减1，再进行相同的操作。
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
		vector<int> result;
		if(!matrix.size() || !matrix[0].size())
			return result;
		
		int left = 0, right = matrix[0].size() - 1;
		int up = 0, down = matrix.size() - 1;
		int i, j;
		while(right >= left && down >= up)
		{
			for(i = left; i <= right; i++)
				result.push_back(matrix[up][i]);
			for(i = up + 1; i <= down; i++)
				result.push_back(matrix[i][right]);
                if(down > up) //如果只剩一行时，这个循环不触发
			for(i = right - 1; i >= left; i--)
				result.push_back(matrix[down][i]);
                if(right > left) //如果只剩一列时，这个循环不触发
			for(i = down - 1; i >= up + 1; i--)
				result.push_back(matrix[i][left]);
			left++;right--;up++;down--;
		}
		return result;
    }

};

发表于 2016-09-16 20:07:37 回复(0)

xiao_lai

#define INFINITE 999999
class Solution {
public:
    vector<int> spiralOrder(vector<vector<int> > &matrix) {
        vector<int> res;
        int order[4][2] = {{0,1},{1,0},{0,-1},{-1,0}};  //右，下，左，上；  
        int row = matrix.size();
        int count=0,index=0;
        if(row==0)return res;  //对特殊情况的判断很关键
        int col = matrix[0].size();
        int i=0,j=-1;
        while(count<row*col){
            int ii = i+order[index][0];
            int jj = j+order[index][1];
            if((ii>=0&&ii<row)&&(jj>=0&&jj<col)&&matrix[ii][jj]!=INFINITE){
                i += order[index][0];
                j += order[index][1];
                res.push_back(matrix[i][j]);
                matrix[i][j]=INFINITE;
                count++;
            }else{//改变方向
                index++;
                if(index==4)index=0;
            }
        }
        return res;
    }
};

发表于 2016-06-25 15:52:09 回复(0)

螺旋矩阵

输入

输出

输入

输出

问题信息

热门推荐

通过挑战的用户

相关试题