题目描述

blablabla

样例

blablabla

被这道题难住了，绞尽脑汁实现了一个时间复杂度O(n^2)，空间复杂度O(1)的代码

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        if(matrix.empty() || matrix[0].empty()) return {};
        int n = matrix.size(), m = matrix[0].size();
        int il[2] = {0, n - 1}, jl[2] = {0, m - 1};
        bool tag = 1;//变i还是变j
        int flag = 0, i = 0, j = 0; //(flag>>1) & 1可以维护一个0,0,1,1,0,0,1,1,...的序列，表示递增还是递减。
        vector<int> ans;
        while(il[0] <= il[1] && jl[0] <= jl[1]){
            if(tag && !((flag>>1) & 1)){
                for(j = jl[0]; j <= jl[1]; j ++) ans.push_back(matrix[i][j]);
                j--;
                il[0] ++;
            }
            else if(!tag && !((flag>>1) & 1)){
                for(i = il[0]; i <= il[1]; i ++) ans.push_back(matrix[i][j]);
                i--;
                jl[1] --;                
            }
            else if(tag && ((flag>>1) & 1)){
                for(j = jl[1]; j >= jl[0]; j --) ans.push_back(matrix[i][j]);
                j++;
                il[1] --;
            }
            else{
                for(i = il[1]; i >= il[0]; i --) ans.push_back(matrix[i][j]);
                i++;
                jl[0] ++;
            }
            flag ++, tag = 1 - tag;
        }
        return ans;
    }
};

终于让我写出一种简短且空间复杂度为O(1)的代码，tag每次取反表示当前要操作的是 i 还是 j ，dx, dy数组表示当前要走的方向，m，n表示当前方向要走的长度。

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        if(matrix.empty() || matrix[0].empty()) return {};
        const int dx[] = {0, 1, 0, -1}, dy[] = {1, 0, -1, 0};
        int n = matrix.size(), m = matrix[0].size();
        bool tag = 1;
        int flag = 0, i = 0, j = -1;//因为第一步向右走，起始位置表示为（0，-1）
        vector<int> ans;
        while(n && m){
            int f = flag % 4, end = tag ? m : n;
            for(int k = 0; k < end; k ++){
                i += dx[f], j += dy[f];
                ans.push_back(matrix[i][j]);
            }
            m -= 1 - tag, n -= tag;
            flag ++, tag = 1 - tag;
        }
        return ans;
    }
};