題?描述

輸??個矩陣，按照從外向?以順時針的順序依次打印出每?個數(shù)字，例如，如果輸?如下4 X 4 矩陣：

則依次打印出數(shù)字 1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10 .

思路及解答

邊界收縮法（推薦）

我們使?的是不斷縮?矩陣上，下，左，右四個邊界的?法。?先定義?個up （上邊界為0 ）, down (下邊界為matrix.length - 1 )， left （左邊界為0 ）， right （右邊界為matrix[0].length - 1 ）。

從第?個?第?個開始打印，向左邊界遍歷到右邊界，之后將上邊界加上1 （因為已經(jīng)遍歷完成上邊界??），判斷上邊界加上?之后是否?于下邊界，如果是則調(diào)出。

之后執(zhí)?類型操作，從上到下，從右到左，從下到上。

具體思路如下：

1. 定義四個邊界：上(up)、下(down)、左(left)、右(right)
2. 按照順時針方向遍歷當前層：
   • 從左到右遍歷上邊界
   • 從上到下遍歷右邊界
   • 從右到左遍歷下邊界
   • 從下到上遍歷左邊界
3. 遍歷完一層后，收縮邊界進入下一層

public class Solution {
    public ArrayList<Integer> printMatrix(int[][] matrix) {
        ArrayList<Integer> results = new ArrayList();
        
        if (matrix != null && matrix.length > 0) {
            int left = 0;
            int right = matrix[0].length - 1;
            int up = 0;
            int down = matrix.length - 1;
            int i;
            while (true) {
                for (i = left; i <= right; i++) {
                    results.add(matrix[up][i]);
                }
                if ((++up) > down) {
                    break;
                }
                for (i = up; i <= down; i++) {
                    results.add(matrix[i][right]);
                }
                if (--right < left) {
                    break;
                }
                for(i=right;i>=left;i--){
                    results.add(matrix[down][i]);
                }
                if(--down<up){
                    break;
                }
                for(i=down;i>=up;i--){
                    results.add(matrix[i][left]);
                }
                if(++left>right){
                    break;
                }
            }
        }
    	return results;
    }
}

注意： (++up) > down 代表 up=up+1;up>dowm 兩個語句。

• 時間復雜度?：O(mn)，每個元素被訪問一次
• 空間復雜度?：O(1)，除了輸出結(jié)果外只使用了固定數(shù)量的變量

方向模擬法

模擬順時針移動的路徑，按照右→下→左→上的方向順序遍歷：

1. 定義四個方向向量表示移動方向
2. 使用一個二維數(shù)組記錄已訪問的位置
3. 當遇到邊界或已訪問的位置時，順時針旋轉(zhuǎn)方向

public List<Integer> printMatrix(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    if (matrix == null || matrix.length == 0) return result;
    
    int rows = matrix.length, cols = matrix[0].length;
    boolean[][] visited = new boolean[rows][cols];
    int[][] directions = {{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
    int directionIndex = 0;
    int row = 0, col = 0;
    
    for (int i = 0; i < rows * cols; i++) {
        result.add(matrix[row][col]);
        visited[row][col] = true;
        
        int nextRow = row + directions[directionIndex][0];
        int nextCol = col + directions[directionIndex][1];
        
        if (nextRow < 0 || nextRow >= rows || nextCol < 0 || nextCol >= cols 
            || visited[nextRow][nextCol]) {
            directionIndex = (directionIndex + 1) % 4;
        }
        
        row += directions[directionIndex][0];
        col += directions[directionIndex][1];
    }
    return result;
}

• 時間復雜度?：O(mn)
• ?空間復雜度?：O(mn)，需要額外的visited數(shù)組

遞歸分解法

將矩陣分解為外層和內(nèi)層，遞歸處理：

1. 遍歷當前矩陣的最外層
2. 將剩余部分作為新矩陣遞歸處理
3. 遞歸終止條件：矩陣為空或只剩一行/一列

public List<Integer> printMatrix(int[][] matrix) {
    List<Integer> result = new ArrayList<>();
    if (matrix == null || matrix.length == 0) return result;
    spiralHelper(matrix, 0, matrix.length - 1, 0, matrix[0].length - 1, result);
    return result;
}

private void spiralHelper(int[][] matrix, int top, int bottom, int left, int right, List<Integer> result) {
    if (left > right || top > bottom) return;
    
    // 遍歷上邊
    for (int i = left; i <= right; i++) {
        result.add(matrix[top][i]);
    }
    
    // 遍歷右邊
    for (int i = top + 1; i <= bottom; i++) {
        result.add(matrix[i][right]);
    }
    
    if (top < bottom && left < right) { // 防止單行或單列
        // 遍歷下邊
        for (int i = right - 1; i >= left; i--) {
            result.add(matrix[bottom][i]);
        }
        
        // 遍歷左邊
        for (int i = bottom - 1; i > top; i--) {
            result.add(matrix[i][left]);
        }
    }
    
    // 遞歸處理內(nèi)層
    spiralHelper(matrix, top + 1, bottom - 1, left + 1, right - 1, result);
}

• 時間復雜度?：O(mn)
• ?空間復雜度?：O(min(m,n))，遞歸棧的深度