---

這題有兩個做法：

1. 把螺旋矩陣做出來，然後輸出該螺旋矩陣 (i, j) 的值，時間複雜度 O(n^2)
2. 觀察螺旋矩陣的規律，直接把對應的值「算」出來，時間複雜度 O(n)

 

第一種方法可以拿 50% 的分數(順利的話)，但另外 50% 的測資的 n 可能會很巨大 (1 ≤ n ≤ 30,000)，這時再把螺旋矩陣做出來就顯得不太理智了。

當然，你可以在製作螺旋矩陣時，遇到 (i, j) 就直接 break 掉，這確實可以提高效率

但最差情況下，若 (i, j) 很接近矩陣中心時，就還是得把幾乎整個矩陣做出來

你可以想像一下一個 30000 x 30000 的螺旋矩陣需要做多久

 

所以需要觀察一下螺旋矩陣的規律

以 4x4 矩陣為例

第一步，把螺旋矩陣看成是像洋蔥一樣，一層層的的矩陣

從外往內數

第一層為 1-12

第二層為 13-16

 

每一層的數字我們都可以分成 4 個部分，每個部分的數字數量皆相同

這樣就可以直接計算每層分別有幾個數字了

由外而內開始數

第一層共有 4 x 3 個元素

第二層共有 4 x 1 個元素

第 k 層共有 4 x (n - 2(k - 1) - 1) 個元素

 

知道每一層的元素總數，就可以直接計算第 ? 層的的所有數值，不用考慮其他內容

這樣就可以不用把一整個螺旋矩陣都做出來

 

那......該如何得知 (i, j) 在第幾層呢?

我們判斷第幾層的方式是從最外圈開始往內數，數到第幾個就是第幾層

所以這邊只需要計算 (i, j) 距離矩陣邊緣有多遠就可以了

注意矩陣有四條邊，所以要算四個距離，取最小值

 

現在有 (i, j) 在第幾層的資料，有那一層的元素總數

剩下要做的就是計算那一層的數字了

最後這部分就讓大家自己來吧

 

提示: 等差數列

 

 

 

補充：

如果你需要更多螺旋矩陣，方便你觀察的話......

n = 5

 

n = 6

 

n = 7

 

n = 10