示意圖:

思路：

這題也是卡了我很久。

初次接觸這種題型, 我覺得可以先把圖畫出來, 先定義一下邏輯該怎麼走, 再來思考該怎麼實作 可參考上圖, 不同顏色代表不同的方向, 以及每次 insert 的範圍。

由上圖可以得到一些資訊

(1) 第一層的 offset 為 1

(2) 第二層開始, 每層的 offset 固定為 2

(3) 若 $n / 2 !== 0, 則會有中間單獨一個數字存在, 其位置為 $res[floor($n / 2)][floor($n / 2)]

(4) 可以看到, 輸出會是 [$n 個 array]

(5) 共有 $n 層

有了上面歸納出的規則, 我們就可以開始實作, 具體參考代碼

由於需要 insert $n 的二次方個數, 所以時間複雜度會是 O(n 的平方)

• 題目連結
• solution example in PHP

class Solution {

    /**
     * @param Integer $n
     * @return Integer[][]
     */
    function generateMatrix($n) {
        $res = array_fill(0, $n, array_fill(0, $n, 0));
        $loop = $mid = (int) ($n / 2);
        $x = $y = 0;
        $offset = 1;
        $count = 1;
        
        while ($loop > 0) {
            $i = $x;
            $j = $y;
            
            for (; $i < $x + $n - $offset; $i++) {
                $res[$j][$i] = $count++;
            }
            
            for (; $j < $y + $n - $offset; $j++) {
                $res[$j][$i] = $count++;
            }
            
            for (; $i > $x; $i--) {
                $res[$j][$i] = $count++;
            }
            
            for (; $j > $y; $j--) {
                $res[$j][$i] = $count++;
            }
            
            $loop--;
            $x++;
            $y++;
            $offset+=2;
        }
        
        if ($n%2 !== 0) {
            $res[$mid][$mid] = $count;
        }
        
        return $res;
    }
}