[演算法題目] Spiral Traverse

本題資訊

難度：medium
使用語言：C++
相關概念：Arrays

題目敘述

Given an m x n matrix, return all elements of the matrix in spiral order.

題目很簡單，給定 \(m \times n\) 的矩陣，希望能以螺旋方式列印出每個值。所謂的螺旋直接以下圖說明會比較容易：

沿著藍色路徑列印出每個值，回傳新的矩陣為：\([1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7]\)。

Idea

理解題目後，其實蠻多想法的。其中一個較為有趣的想法是類似寫遊戲那樣，用方向座標來移動，碰到牆面就轉往指定方向（類似貪吃蛇），不過複雜度好像會提升，希望以後回顧這一題能夠為這種版本寫出較為好的答案。

目前這個版本是比較平舖直述的。依螺旋巡覽的定義，我們變換完四個方向後，就會再次以相同模式繼續跑完整個流程直到結束，所以勢必會有個 loop 在做「走四個方向」這一件事。也需要判斷目前哪一列、哪一欄已經跑過，無須重複巡覽。

初步想法寫完後，測試依然不通過，原來是沒考慮到較為狹長的矩陣，像是：

$$
\begin{bmatrix}
1 & 5 \\
2 & 6 \\
3 & 7 \\
4 & 8 \\
\end{bmatrix} \text{ or }
\begin{bmatrix}
1 & 2 & 3 & 4 \
\end{bmatrix}
$$

沒考慮到的點是可能會提前跳出而不是硬要走完每個方向。

想法簡單，做起來相對繁瑣一點點。設定 startRow 和 startCol 為起始列和起始欄的 index，endRow 和 endCol 為結束列和結束欄的 index，result 是最後輸出的結果。

• 若矩陣沒有東西，則 return 一個空的陣列。
• 重複以下循環，直到 startRow 大於 endRow 且 startCol 大於 endCol：
  1. starRow 那一列由左至右依序將元素放進 result 直到 endCol 那一欄，startRow + 1。
  2. endCol 那一欄由上至下依序將元素放進 result 直到 endRow 那一列，endCol – 1。
  3. endRow 那一列由右至左依序將元素放進 result 直到 startCol 那一欄，endRow – 1。
  4. startCol 那一欄由下至上依序將元素放進 result 直到 starRow 那一列，startCol + 1。
• 回傳 result。

這邊要注意的是因為會有類似 \(9 \times 1\) 矩陣的狀況，導致其實前兩步驟都巡覽完了，第 3 步驟和第 4 步驟便是多餘的，因此需要在這兩個步驟裡再加入判斷，是否起始欄或列的 index 已經超過末端欄或列的 index，如果有這種奇葩狀況就直接 break。

using namespace std;

vector<int> spiralTraverse(vector<vector<int>> array) {
  vector<int> result = {};
  int startRow = 0;
  int endRow = array.size() - 1;
  int startCol = 0;
  int endCol = array[0].size() - 1;

  if (array.size() == 0){
    return {};
  }

  while (startRow <= endRow && startCol <= endCol){
    for (int c = startCol; c <= endCol; c++){
      result.push_back(array[startRow][c]);
    }
    startRow++;
    for (int r = startRow; r <= endRow; r++){
      result.push_back(array[r][endCol]);
    }
    endCol--;
    for (int c = endCol; c >= startCol; c--){
      if (startRow > endRow) break;
      result.push_back(array[endRow][c]);
    }
    endRow--;
    for (int r = endRow; r >= startRow; r--){
      if (startCol > endCol) break;
      result.push_back(array[r][startCol]);
    }
    startCol++;
  }
  return result;
}

時間複雜度：\(O(n)\)，\(n\) 是矩陣的元素個數。
空間複雜度：\(O(n)\)