剑指offer18

剑指offer18：顺时针打印矩阵

题目描述

题目描述
输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，
如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 
则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

解法一：基于规律的方法

class Solution {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        int row = matrix.size(), col = matrix[0].size();
        vector<int>res;
        if (row == 0 || col == 0) return res;
        int left = 0, right = col - 1, top = 0, btm = row - 1;
        while (left <= right&&top <= btm)
        {
            for (int i = left; i <= right; i++)
                res.push_back(matrix[top][i]);
            top++;//打印完最上面 上标志往下移

            for (int i = top; i <= btm; i++)
                res.push_back(matrix[i][right]);
            right--;//打印完最右边 右标志往左移

            if (top <= btm)//防止出现一行的情况 会重复
                for (int i = right; i >= left; i--)
                    res.push_back(matrix[btm][i]);
            btm--;//打印完最下面  下标志上移

            if (right >= left)//防止出现一列的情况 会重复
                for (int i = btm; i >= top; i--)
                    res.push_back(matrix[i][left]);
            left++;//打印完最左边   左标志右移；
        }
        return  res;
    }
};

解法二：基于四个标记的方法

class Solution2 {
public:
    vector<int> printMatrix(vector<vector<int> > matrix) {
        vector<int> a;
        int row = matrix.size();  //定义矩阵行
        int column = matrix[0].size(); //定义矩阵列
        int x = 0, y = 0, endx = column - 1, endy = row - 1;
        int i, j, k, m;
        while (x <= endx&&y <= endy)
        {
            for (i = x; i <= endx; ++i)
                a.push_back(matrix[x][i]);
            for (j = y + 1; j <= endy; ++j)
                a.push_back(matrix[j][endx]);
            if (y != endy)
                for (k = endx - 1; k >= x; --k)
                    a.push_back(matrix[endy][k]);
            if (x != endx)
                for (m = endy - 1; m >= y + 1; --m)
                    a.push_back(matrix[m][x]);
            x++; y++;
            endx--; endy--;
        }
        return a;
    }
};

main函数

#include "stdafx.h"
#include <vector>
#include <iostream>
using namespace std;

int main()
{
    vector<vector<int>> nums;
    int row, col;
    cout << "请输入矩阵的行row:" << endl;
    cin >> row;
    cout << "请输入矩阵的列col:" << endl;
    cin >> col;
    int currval;
    cout << "请输入矩阵的数据" << endl;
    for(int i=0;i<row;i++)
        for (int j = 0; j < col; j++)
        {
            cin >> currval;
            nums[i][j] = currval;
        }
    Solution a;
    vector<int> ans(row*col,0);
    ans = a.printMatrix(nums);
    for (auto n : ans)
        cout << n << ' ';

    system("pause");
    return 0;
}