【杂题】剑指 Offer 29. 顺时针打印矩阵-跟着帅地玩副业，开拓第二曲线PlayOffer

YULONG 永久会员 2024年10月25日下午3:59

// 方法一：模拟
// 解题思路：从起点（0，0）开始，按照右-下-左上的方式遍历数组，遇到边界或者已访问的元素，
// 更换到下一个方向，遍历完所有元素结束
// 时间复杂度 O(mn), 空间复杂度O(mn)

// 方法二：按层遍历
// 解题思路：每层为最外圈数组元素，可分成上右下左四个部分
// 每层上部分起点为[top, left],终点为[top, right]
// 每层右部分起点为[top+1, right],终点为[down, right]
// 每层下部分起点为[down, right-1],终点为[down, left+1]
// 每层左部分起点为[down, left],终点为[up+1, left]
// 遍历时候判断该层的元素长度是否 > 0
// 继续下一层 top++,down–,left++,right–直到遍历完 mn个元素
// 时间复杂度 O(mn), 空间复杂度O(1)

class Solution {
    // 方法1
    public int[] spiralArray1(int[][] array) {
        if (array == null || array.length == 0){
            return new int[]{};
        }
        int m = array.length, n = array[0].length;

        int[] xdir = new int[]{0, 1, 0, -1};
        int[] ydir = new int[]{1, 0, -1, 0};
        int d = 0;

        int[] vis = new int[m*n];
        int i = 0, j = 0;
        int[] ans = new int[m*n];
        for (int k = 0; k < m * n; k++){
            ans[k] = array[i][j];
            vis[i * n + j] = 1;

            int ni = i + xdir[d];
            int nj = j + ydir[d];
            if (ni < 0 || ni >= m || nj < 0 || nj >= n || (vis[ni * n + nj] == 1)){
                d = (d + 1) % 4;
                ni = i + xdir[d];
                nj = j + ydir[d];
            }
            i = ni;
            j = nj;
        }
        return ans;

    }

    // 方法2
    public int[] spiralArray(int[][] array) {
        if (array == null || array.length == 0){
            return new int[]{};
        }
        int m = array.length, n = array[0].length;

        int[] ans = new int[m*n];
        int idx = 0;

        int top = 0, left = 0, right = n-1, down = m - 1;

        while (idx < m * n){

            // 遍历上层
            for (int i = 0; i < right - left + 1; i++){
                ans[idx++] = array[top][left+i];
            }

            // 遍历右层
            if (top < down){
                for (int i = 0; i < down - top; i++){
                    ans[idx++] = array[top+i+1][right];
                }
            }

            // 遍历下层
            if (left < right && top < down){
                for (int i = 0; i < right - left - 1; i++){
                    ans[idx++] = array[down][right-1-i];
                }
            }

            // 遍历左层
            if (left < right && top < down){
                for (int i = 0; i < down - top; i++){
                    ans[idx++] = array[down-i][left];
                }
            }

            // 缩圈继续遍历
            top++;
            right--;
            left++;
            down--;
        }

        return ans;

    }
}

0 赞同 0 条回复

王位詮釋普通 2024年4月15日下午3:10

class Solution {
    public int[] spiralArray(int[][] array) {
        if(array==null||array.length==0){
            return new int[0];
        }
        int m = array.length;
        int n = array[0].length;
        int[] res = new int[m*n];
        int up = 0;//上边界
        int down = m-1;//下边界
        int left = 0;//左边界
        int right = n-1;//右边界
        int index = 0;
        while(up<=down||left<=right){
            //往右走
            for(int i=left;i<=right;i++){
                res[index++] = array[up][i];
            }
            up++;
            if(up>down){
                break;
            }
            //往下走
            for(int i=up;i<=down;i++){
                res[index++] = array[i][right];
            }
            right--;
            if(right<left){
                break;
            }
            //往左走
            for(int i = right;i>=left;i--){
                res[index++] = array[down][i];
            }
            down--;
            if(down<up){
                break;
            }
            //往上走
            for(int i = down;i>=up;i--){
                res[index++] = array[i][left];
            }
            left++;
            if(left>right){
                break;
            }
        }
        return res;
    }
}
思路：定义左边界、有边界、上边界和下边界，然后可以向右走、向下走、
向左走和向上走，同时创建一个res数组用来保存访问到的数组元素
时间复杂度：O(mn)
空间复杂度：O(1)

0 赞同 0 条回复

紫芝普通 2024年4月12日上午9:52

思路：模拟顺时针打印矩阵，需要注意边界情况

“`c++
class Solution {
public:
vector spiralArray(vector>& array) {
if (array.empty()) return {};
int m = array.size(), n = array[0].size();
vector ans(m*n, 0);
int idx = 0;
int l = 0, r = n-1, t = 0, b = m-1;
while (true) {
// top row: t, j = [l -> r]
for (int j=l; j<=r; j++) { ans[idx++] = array[t][j]; } // top row is over. if (++t > b) break;
// right col: i = [t -> b], r
for (int i=t; i<=b; i++) { ans[idx++] = array[i][r]; } // right col is over. if (--r < l) break; // bottom row: b, j = [r -> l]
for (int j=r; j>=l; j–) {
ans[idx++] = array[b][j];
}
// bottom row is over.
if (–b < t) break; // left col: i = [b -> l], l
for (int i=b; i>=t; i–) {
ans[idx++] = array[i][l];
}
// left col is over.
if (++l > r) break;
}
return ans;
}
};
“`

0 赞同 0 条回复

白雪公主倒拔垂杨柳永久会员 2024年4月10日下午5:33

class Solution {
    public int[] spiralArray(int[][] array) {
        if(array==null || array.length==0 || array[0].length ==0) return new int[0];

        //记录可移动的列数的范围
        int l=0;
        int r=array[0].length-1;
        // 记录可移动的行数的范围
        int t = 0;
        int b=array.length-1;

        //用于保存结果的数组
        int[] res = new int[(r+1) * (b+1)];
        int index=0;

        while(true){
            //→
            for(int i=t,j=l;j<=r;j++) res[index++]=array[i][j];
            if(++t>b) break; //下次→只能从++b行开始了

            // ↓
            for(int i=t,j=r;i<=b;i++) res[index++]=array[i][j];
            if(l>--r) break; //下次↓只能从--r列开始了

            //←
            for(int i=b,j=r;j>=l;j--) res[index++]=array[i][j];
            if(t>--b) break;//下次→只能从--b行开始了

            //↑
            for(int i=b,j=l;i>=t;i--)  res[index++]=array[i][j];
            if(++l>r) break;//下次↑只能从++l列开始了
        }

        return res;
    }
}

时间复杂度：O(nm)
额外空间复杂度：O(nm)

0 赞同 0 条回复

Jimmy 普通 2024年4月9日下午9:49

死循环中按照右下左上的顺序依次提取元素，每次提取一个元素之后都要判断还能否继续遍历

class Solution {
public:
    vector<int> spiralArray(vector<vector<int>>& array) {
        vector<int> ans;
        if(array.size() == 0)return ans;
        int left = 0;
        int right = array[0].size()-1;
        int upper = 0;
        int down = array.size()-1;
        while(true)
        {
            for(int j=left;j<=right;j++)ans.push_back(array[upper][j]);
            if(++upper>down)break;
            for(int i=upper;i<=down;i++)ans.push_back(array[i][right]);
            if(--right<left)break;
            for(int j=right;j>=left;j--)ans.push_back(array[down][j]);
            if(--down < upper)break;
            for(int i=down;i>=upper;i--)ans.push_back(array[i][left]);
            if(++left > right)break;
        }
        return ans;
    }
};

0 赞同 0 条回复

云无深雁影普通 2024年4月9日下午8:14

class Solution {
public int[] spiralArray(int[][] array) {
if(array.length 0)
return new int[0];
int[] ans = new int[array.length * array[0].length];
ans[0] = array[0][0];
int count = 1;
int left = 0;
int right = array[0].length – 1;
int top = 0;
int bottom = array.length – 1;
int direction = 0;//右下左上
int i = 0, j = 0;
while(left <= right && top <= bottom ){

        switch(direction){
            case 0:                    
                if(j + 1 <= right){
                    j++; 
                }
                else{
                    direction = 1;
                    top++;
                    continue;
                }
                ans[count++] = array[i][j];
                break;
            case 1:
                if(i + 1 <= bottom){
                    i++; 
                }
                else{
                    direction = 2;
                    right--;
                    continue;
                }
                ans[count++] = array[i][j];
                break;
            case 2:
                if(j - 1 >= left){
                    j--; 
                }
                else{
                    direction = 3;
                    bottom--;
                    continue;
                }
                ans[count++] = array[i][j];
                break;
            case 3:
                if(i - 1 >= top){
                    i--; 
                }
                else{
                    direction = 0;
                    left++;
                    continue;
                }
                ans[count++] = array[i][j];
                break;

        }
    }


    return ans;



}

}
//空间复杂度Onm
时间复杂度Onm

0 赞同 0 条回复

【杂题】剑指 Offer 29. 顺时针打印矩阵

共以下 6 个回答

# 回答此问题取消回复

【杂题】剑指 Offer 29. 顺时针打印矩阵

共以下 6 个回答

# 回答此问题 取消回复

# 回答此问题取消回复