漫畫：如何螺旋遍歷二維數(shù)組？
在周一發(fā)布的漫畫當中，小灰忽略了一個小問題：
當二維數(shù)組的最內(nèi)層只有一行或一列時，螺旋遍歷有可能重復訪問。因此必須在第3和第4個小循環(huán)中加上額外的條件限制。
今天出了一個修訂版，修正了這個缺陷。
非常感謝大家的指正。
—————? 第二天? —————
什么意思呢？我們來舉個例子，給定下面這樣一個二維數(shù)組：
我們需要從左上角的元素1開始，按照順時針進行螺旋遍歷，一直遍歷完所有的元素，遍歷的路徑就像下圖一樣：
經(jīng)過這樣的遍歷，返回的元素結(jié)果如下：
1，2，3，4，5，10，15，20，19，18，17，16，11，6，7，8，9，14，13，12
————————————
第1層
從左到右遍歷“上邊”：
從上到下遍歷“右邊”：
從右到左遍歷“下邊”：
從下到上遍歷“左邊”：
第2層
從左到右遍歷“上邊”：
從上到下遍歷“右邊”：
從右到左遍歷“下邊”：
從下到上遍歷“左邊”：
第3層
從左到右遍歷“上邊”：
從上到下遍歷“右邊”：
從右到左遍歷“下邊”：
第三層的“左邊”已無需遍歷，二維數(shù)組到此遍歷完畢。
public?class?SpiralOrder?{
????public?static?List?spiralOrder(int[][]?matrix)? {
????????List?list?=?new?ArrayList();
????????//當二維數(shù)組是空或任何一個維度是0，直接返回
????????if?(matrix?==?null?||?matrix.length?==?0?||?matrix[0].length?==?0)?{
????????????return?list;
????????}
????????//m是矩陣的行數(shù)
????????int?m?=?matrix.length;
????????//n是矩陣的列數(shù)
????????int?n?=?matrix[0].length;
????????//二維數(shù)組的層數(shù)，取決于行和列的較小值
????????int?size?=?(Math.min(m,?n)+1)/2;
????????//大循環(huán)，從外向內(nèi)逐層遍歷矩陣
????????for(int?i=0;?i????????????//從左到右遍歷“上邊”
????????????for?(int?j=i;?j????????????????list.add(matrix[i][j]);
????????????}
????????????//從上到下遍歷“右邊”
????????????for?(int?j=i+1;?j????????????????list.add(matrix[j][(n-1)-i]);
????????????}
????????????//從右到左遍歷“下邊”
????????????for?(int?j=i+1;?j1)-i>i;?j++)?{
????????????????list.add(matrix[(m-1)-i][(n-1)-j]);
????????????}
????????????//從下到上遍歷“左邊”
????????????for?(int?j=i+1;?j1-i?&&?i<(n-1)-i;?j++)?{
????????????????list.add(matrix[(m-1)-j][i]);
????????????}
????????}
????????return?list;
????}
????public?static?void?main(String[]?args)?{
????????int[][]?matrix?=?{
????????????????{?1,??2,??3,??4,??5??},
????????????????{?6,??7,??8,??9,??10?},
????????????????{?11,?12,?13,?14,?15?},
????????????????{?16,?17,?18,?19,?20?}
????????};
????????int[][]?matrix2?=?{
????????????????{?1,??2,??3?},
????????????????{?4,??5,??6?},
????????????????{?7,??8,??9?},
????????????????{?10,?11,?12?},
????????????????{?13,?14,?15?}
????????};
????????List?resultList1?=?spiralOrder(matrix);
????????System.out.println(Arrays.toString(resultList1.toArray()));
????????List?resultList2?=?spiralOrder(matrix2);
????????System.out.println(Arrays.toString(resultList2.toArray()));
????}
}
在上面的代碼中，一個大循環(huán)當中包含了4個小循環(huán)。大循環(huán)控制了每一層的遍歷，4個小循環(huán)分別實現(xiàn)了同一層上邊、右邊、下邊，左邊的遍歷。
當遍歷到最內(nèi)層時，4個小循環(huán)并不會全都執(zhí)行，比如測試代碼中matrix2的最內(nèi)層就只有一列，此時只需要遍歷“上邊”和“右邊”。
這種情況下，遍歷“下邊”和“左邊”的小循環(huán)必須加上了額外的條件限制：
(m-1)-i>i
i<(n-1)-i
使得同一條邊不會被重復遍歷到。
—————END—————
喜歡本文的朋友，歡迎關注公眾號?程序員小灰，收看更多精彩內(nèi)容
點個[在看]，是對小灰最大的支持！
免責聲明：本文內(nèi)容由21ic獲得授權后發(fā)布，版權歸原作者所有，本平臺僅提供信息存儲服務。文章僅代表作者個人觀點，不代表本平臺立場，如有問題，請聯(lián)系我們，謝謝！
下載文檔
