【LeetCode】59. Spiral Matrix II

Question link

Link

Intuition

Given a positive integer n, generate an n x n matrix filled with elements from 1 to n2 in spiral order.
給定一個整路n，以迴旋方式產生一個陣列，並將數字從1填充到n2
題目要求以迴旋方式將數字填入到矩陣中，因此我們需要考慮每一個邊，該如何設計迴圈的操作條件，依舊是要堅持迴圈不變量的原則，填充的順序為

• 上列為由左到右
• 右列為由上至下
• 下列為由右至左
• 左列為由下至上

首先決定這樣的操作會循環幾次，如果n是奇數則只要做n / 2次，中間元素最後處理就好，如果是偶數次也是做n / 2次。
接著設計起始位置與終止位置，作為4個邊循環的條件，每次繞完後將起始位置加一，終止位置減一，代表著向內部進行縮圈，在這次實作中保持左必右開的循環原則

Approach

1. 宣告loop變數作為每繞外圈的次數
2. 宣告start_x與start_y作為起始位置的索引
3. 宣告end_x與end_y作為終止位置
4. 宣告count作為元素計數
5. 循環開始
   1. 在start_x固定，沿著y軸循環元素
   2. 在end_y固定，沿著x軸循環元素
   3. 在end_x固定，反方向沿著y軸循環元素
   4. 在start_y固定，沿著x軸循環元素
6. 最後處理中間元素

Complexity

• Time complexity:
  $O(n^2)$
• Space complexity:
  $O(1)$

Code

class Solution {
public:
    vector<vector<int>> generateMatrix(int n) {
        vector<vector<int>> ans(n, vector<int>(n, 0));
        int loop = n / 2;
        int start_x = 0;
        int start_y = 0;
        int end_x = n - 1;
        int end_y = n - 1;
        int count = 1;
        while(loop) {
            for (int i = start_x; i < end_x; i++){
                ans[start_y][i] = count++; 
            }
            for (int i = start_y; i < end_y; i++){
                ans[i][end_x] = count++;
            }
            for (int i = end_x; i > start_x; i--){
                ans[end_y][i] = count++;
            }
            for (int i = end_y; i > start_y; i--){
                ans[i][start_x] = count++;
            }
            start_x++;
            start_y++;
            end_x--;
            end_y--;
            loop--;
        }
        if (n % 2 == 1){
            ans[n / 2][n / 2] = count;
        }
        return ans;
    }
};