当前位置：首页 > article >正文

代码随想录刷题day06|（数组篇）54.螺旋矩阵（补1.13

article 2025/1/15 12:07:02

一、相关算法题目

二、错误代码

三、总结

接day05螺旋矩阵 II

一、相关算法题目

54.螺旋矩阵

54. 螺旋矩阵 - 力扣（LeetCode）

该题和59. 螺旋矩阵 II - 力扣（LeetCode）正好相反，59是按顺时针顺序向二维数组中存放元素，该题是按顺时针顺序从二维数组中读取元素并返回列表。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
       if (matrix.length == 0 || matrix[0].length == 0) return new ArrayList<>();
       int m = matrix.length;
       int n= matrix[0].length;
       int l = 0,t = 0,b = m - 1,r = n - 1;
       List<Integer> list = new ArrayList<>(m*n);
       while(true){
        for(int i = l;i <= r;i++){
            list.add(matrix[t][i]);
        }
        if(++t > b) break;
        for(int i = t;i <= b;i++){
            list.add(matrix[i][r]);
        }
        if(--r < l) break;
        for(int i = r;i >= l;i--){
            list.add(matrix[b][i]);
        }
        if(--b < t) break;
        for(int i = b;i >= t;i--){
            list.add(matrix[i][l]);
        }
        if(++l > r) break;
       }
       return list;
    }
}

二、错误代码

报错代码：超出时间限制

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
       int m = matrix.length;
       int n= matrix[0].length;
       int l = 0,t = 0,b = m - 1,r = n - 1;
       List<Integer> list = new ArrayList<>();
       int num = 1;
       int count = m*n; 
       while(num <= count){
        for(int i = l;i <= r;i++){
            list.add(matrix[t][i]);
        }
        t++;
        for(int i = t;i <= b;i++){
            list.add(matrix[i][r]);
        }
        r--;
        for(int i = r;i >= l;i--){
            list.add(matrix[b][i]);
        }
        b--;
        for(int i = b;i >= t;i--){
            list.add(matrix[i][l]);
        }
        l++;
       }
       return list;
    }
}

超时原因：

1. ArrayList在调用add()方法添加元素时，如果当前数组容量不够，就会进行扩容，扩容会创建一个新的、更大的数组，并将原数组的数据复制到新数组中，导致额外的时间开销；如果要插入大量数据，最好提前设置ArrayList的初始容量，这样ArrayList在一开始就会分配足够空间，避免频繁扩容，提高性能；

改进：

List<Integer> list = new ArrayList<>(m*n);

2.num和count并没有起到真正控制循环的作用，关于num并没有对应条件控制语句，num始终等于1，始终＜count，所以循环不会停止；

3.循环中加上控制语句 num++ ？

不对，本意是想用num表示数组中的元素个数，但是每一次while循环num的增量（+1）和数组中元素被遍历的个数的增量（for循环中是按行遍历）并不相同，即无法用num的增量来控制while循环执行的次数；

4.循环中每个for循环体里面加上（list.add后面）控制语句 num++ ？

也不对，虽然此时两者增量一致，但是当最后一轮，num=11 < 12，进入while循环，执行第一个for循环后，全部元素已经遍历完成，num此时可能会=13，＞12，但是r和l、t和b 相等，for循环继续，list中会继续添加重复元素，又因list中设置了固定容量，那么list可能要扩容，数组变动，可能出现错误。

改进：去掉num，使用边界控制，每遍历完一行或一列后，调整l、t、r、b，并检查是否到达结束条件；