來(lái)自公眾號(hào)：程序員小灰

————— 第二天 —————

什么意思呢？我們來(lái)舉個(gè)例子，給定下面這樣一個(gè)二維數(shù)組：

我們需要從左上角的元素1開始，按照順時(shí)針進(jìn)行螺旋遍歷，一直遍歷完所有的元素，遍歷的路徑就像下圖一樣：

經(jīng)過(guò)這樣的遍歷，返回的元素結(jié)果如下：

1，2，3，4，5，10，15，20，19，18，17，16，11，6，7，8，9，14，13，12

————————————

第1層

從左到右遍歷“上邊”：

從上到下遍歷“右邊”：

從右到左遍歷“下邊”：

從下到上遍歷“左邊”：

第2層

從左到右遍歷“上邊”：

從上到下遍歷“右邊”：

從右到左遍歷“下邊”：

從下到上遍歷“左邊”：

第3層

從左到右遍歷“上邊”：

從上到下遍歷“右邊”：

從右到左遍歷“下邊”：

第三層的“左邊”已無(wú)需遍歷，二維數(shù)組到此遍歷完畢。

publicclassSpiralOrder{ publicstaticListspiralOrder(int[][]matrix){ Listlist=newArrayList(); //當(dāng)二維數(shù)組是空或任何一個(gè)維度是0，直接返回 if(matrix==null||matrix.length==0||matrix[0].length==0){ returnlist; } //m是矩陣的行數(shù) intm=matrix.length; //n是矩陣的列數(shù) intn=matrix[0].length; //二維數(shù)組的層數(shù)，取決于行和列的較小值 intsize=(Math.min(m,n)+1)/2; //大循環(huán)，從外向內(nèi)逐層遍歷矩陣 for(inti=0;ii;j++){ list.add(matrix[(m-1)-i][(n-1)-j]); } //從下到上遍歷“左邊” for(intj=i+1;jresultList1=spiralOrder(matrix); System.out.println(Arrays.toString(resultList1.toArray())); ListresultList2=spiralOrder(matrix2); System.out.println(Arrays.toString(resultList2.toArray())); } }

在上面的代碼中，一個(gè)大循環(huán)當(dāng)中包含了4個(gè)小循環(huán)。大循環(huán)控制了每一層的遍歷，4個(gè)小循環(huán)分別實(shí)現(xiàn)了同一層上邊、右邊、下邊，左邊的遍歷。

當(dāng)遍歷到最內(nèi)層時(shí)，4個(gè)小循環(huán)并不會(huì)全都執(zhí)行，比如測(cè)試代碼中matrix2的最內(nèi)層就只有一列，此時(shí)只需要遍歷“上邊”和“右邊”。

這種情況下，遍歷“下邊”和“左邊”的小循環(huán)必須加上了額外的條件限制：

(m-1)-i>i

i<(n-1)-i

使得同一條邊不會(huì)被重復(fù)遍歷到。

責(zé)任編輯：PSY

原文標(biāo)題：漫畫：如何螺旋遍歷二維數(shù)組？

文章出處：【微信公眾號(hào)：算法與數(shù)據(jù)結(jié)構(gòu)】歡迎添加關(guān)注！文章轉(zhuǎn)載請(qǐng)注明出處。