二維陣列就是這麼簡單
一、背景
這篇文章主要通過幾個具體的例子來看怎麼使用二維陣列。
二、二維陣列
二維陣列和一維陣列一樣,也是有一系列元素組成。
但是二維陣列的元素排列在矩形網格里,而不是一條直線。
當然,有些語言裡面,二維陣列是通過一維陣列實現的,而在其他一些語言中,則不存在二維陣列的概念。
例如在 C/C++
中,二維陣列底層儲存為一維陣列。
下圖顯示了大小為 M * N
的陣列 A 的實際結構:
因此,如果我們將 A 定義為也包含 M * N
個元素的一維陣列,那麼實際上 A[i][j]
就等於 A[i * N + j]
。
而在 Java
中,二維陣列其實就是包含 M
個元素為一維陣列,而每個元素又是一個大小為 N
的一維陣列。
下圖顯示了 Java
中二維陣列 A 的實際結構:
而對於動態二維陣列,則是一維動態陣列的元素還是一維動態陣列。
具體可以看下面的題吧。
三、對角線遍歷
告訴你一個 N * M
的二維陣列,求按對角線遍歷這個二維陣列,並輸出遍歷的元素。
遍歷規則可以參考下圖。
其實這道題看著很簡單,但是做起來會發現很複雜,需要考慮的情況太多。
一會是對角線向上,一會是對角線向下。
一會是左邊越界,一會是右邊越界,或者上邊越界,或者下邊越界。
所以我們需要對這道題進行劃分,來減少邊界情況。
簡單看下上圖,可以發現答案是把對角線拼接起來了。
所以我們可以分三步走。
第一步得到所有的對角線。
第二步判斷對角線是否需要翻轉。
第三步將對角線拼接到答案上。
第一步,我們可以以對角線最小行來劃分。
分兩部分:第一部分最小行是矩陣的上邊,從左到右。第二部分最小行是矩陣的右邊,從上到下。
有了最小行,我們就可以迴圈掃描下一行,列數也依次減一,只要沒越界,都屬於這個對角線上的合法座標。
第二步,可以發現對角線的方向按奇偶性在翻轉,所以我們使用一個flag來標記即可。
第三步就是講對角線的資料拼接到答案上,迴圈拼接即可。
四、螺旋矩陣
給一個 N * M
的矩陣,按順時針輸出所有元素。
上面那道題對角線是兩個方向,現在螺旋遍歷則是四個方向了。
此時需要考慮的特殊情況很多了。
我們逐一寫出所有方向的邏輯也可以,但是很用以漏寫。
面對矩陣的這種問題,常用的方法是模板化。
具體來說就是講所有操作進行抽象提取,劃分為不同的狀態,每個狀態有自己的模板操作。
模板化後的好處是我們可以直接迴圈就可以完成遍歷矩陣了。
比如上面這個程式碼。
第一個是將操作按順時針標號模板化,這樣的好處是我們可以通過運算得到下一個操作。
第二個是將上下左右的邊界 base
進行模板化,同時儲存一個維護邊界的輔助陣列 baseInc
。
第三個是將最關鍵的矩陣遍歷計算規則 xyInc
模板化。
通過上面三個模板化,我們就可以快速判斷當前是不是處理完了(最外層迴圈)。
也可以快速判斷當前方向的遍歷是否完成了(內層迴圈)。
當我們遍歷完一個方向後, x,y
肯定是越界的,所以需要回滾,並轉換到下個方向狀態。
又由於回滾後的座標之前已經處理,所以需要在新的方向移動一下,到達新的未處理的位置。
就這樣,一道很複雜的螺旋遍歷矩陣問題,就轉化為了兩層迴圈的問題了。
五、楊輝三角
輸入一個數字 N
,輸出高度為 N
的楊輝三角。
注:楊輝三角參考下圖。
這道題與前面兩道題相比就簡單多了。
根據動圖中的效果,我們可以發現一個規律:下一行某個位置的值時上一行相同位置和前一個位置值的和。
即 f(x, y) = f(x-1, y) + f(x-1, y-1)
。
而對於第一個和最後一個,不滿足上面的規律(越界了),但是都是 1
。
於是我們就可以按照這個規律寫出答案了。
七、最後
在二維數組裡面,對角線遍歷和螺旋遍歷就有點技術含量了。
當然,對於計算機專業的人來說,那個在學習第一門語言的時候,大家肯定都實現過這樣的問題的。
這裡主要是提供一種思路,可以較為方便的處理這個問題。
如果你有更好的思路,可以告訴我。
-EOF-