【圖解算法】螺旋矩陣、旋轉(zhuǎn)矩陣、“之”型輸出、矩陣找數(shù)
這幾道矩陣相關(guān)的題目比較考察全局觀，如果陷在思考局部點(diǎn)如何移動，那么在面試中將很難快速解出題目。
問題描述
轉(zhuǎn)圈打印矩陣。【leetcode-54-螺旋矩陣】
旋轉(zhuǎn)正方形矩陣?！緇eetcode-48-旋轉(zhuǎn)圖像】
“之”字型打印矩陣。
在行列都排好序的矩陣中找數(shù)?！咎囟ǖ臄?shù)據(jù)】
轉(zhuǎn)圈打印矩陣
【題目】 給定一個整型矩陣Matrix，請按照順時針轉(zhuǎn)圈的方式打印它。例如:
實(shí)際上存儲結(jié)構(gòu)為二維數(shù)組打印結(jié)果為：
1，2，3，4，8，12，16，15，14，13，9，?5，6，7，11，10
轉(zhuǎn)圈打印【要求】 額外空間復(fù)雜度為O(1)。
【解法說明】
如果我們將眼光局限于坐標(biāo)每次該如何移動，如何判斷矩陣中哪些點(diǎn)已經(jīng)輸出，哪些點(diǎn)還沒有輸出，那么你就是進(jìn)坑里了，這種方法不是不行，但是在面試的場景下，扣各種邊界會導(dǎo)致你非常容易出錯。那么有什么辦法可以快速解決呢？其實(shí)很簡單，從全局來看，我們實(shí)際上是在繪制一個又一個的矩形邊界：
將問題轉(zhuǎn)化為繪制矩形邊界是不是覺得問題一下子簡單了很多，我們只要分別打印四個邊界，就能打印出一個矩形；接下來我們考慮外層和內(nèi)層如何銜接：
如下圖所示，我們每次繪制某一邊界時（如矩形的上邊界），不要把最后一個點(diǎn)繪制了，而是作為下一個邊界的起點(diǎn)，那么最終結(jié)束位置在5，與下一圈的6正好銜接：
內(nèi)外層銜接看到這里大家想必已經(jīng)知道怎么做了，是的，我們只需控制左上角和右下角兩個點(diǎn)的坐標(biāo)，然后每跑完一圈，坐標(biāo)進(jìn)行相應(yīng)的增加或減少即可：
控制對角坐標(biāo)到這里，思路已經(jīng)基本出現(xiàn)了，我們在外層寫一個循環(huán)控制對角坐標(biāo)的變化，內(nèi)部則是打印一個矩形的外邊界的函數(shù)：
void?circlePrint(vector<vector<int>>?&matrix)?{
????if?(matrix.empty())?return;?//?空數(shù)組判斷
????int?a?=?0,?b?=?0,?c?=?matrix.size()?-?1,?d?=?matrix[0].size()?-?1;
????while?(a?<=?c?&&?b?<=?d)?{
????????edgePrint(a++,?b++,?c--,?d--,?matrix);?//?打印(a,b)和(c,d)所在的矩形邊界
????}
}
關(guān)于打印矩形邊界，還需要考慮兩種邊界情況：
打印矩陣的邊界考慮至此，我們就可以很輕松地寫出代碼了：
void?edgePrint(int?a,?int?b,?int?c,?int?d,?vector<vector<int>>?&matrix)?{
????if?(a?==?c)?{?//?only?one?row
????????for?(int?j?=?b;?j?<=?d;?++j)?{
????????????cout?<"?";
????????}
????}?else?if?(b?==?d)?{?//?only?one?column
????????for?(int?i?=?a;?i?<=?c;?++i)?{
????????????cout?<"?";
????????}
????}?else?{
????????for?(int?j?=?b;?j?//?print?up?edge
????????????cout?<"?";
????????}
????????for?(int?i?=?a;?i?//?print?right?edge
????????????cout?<"?";
????????}
????????for?(int?j?=?d;?j?>?b;?--j)?{?//?print?down?edge
????????????cout?<"?";
????????}
????????for?(int?i?=?c;?i?>?a;?--i)?{?//?print?left?edge
????????????cout?<"?";
????????}
????}
}
旋轉(zhuǎn)正方形矩陣
【題目】 給定一個整型正方形矩陣 Matrix，請把該矩陣調(diào)整成順時針旋轉(zhuǎn)90度的樣子。
原地順時針旋轉(zhuǎn)90度【要求】 額外空間復(fù)雜度為O(1)。
【解法說明】注意到題目要求我們的空間復(fù)雜度為O(1)，因此，我們不能借助輔助矩陣，只能原地調(diào)整。咋一看好像無從下手，但只要使用我們前面提到過的全局思想，我們可以首先將問題拆解為將一個矩形邊界旋轉(zhuǎn)90度：
化簡為邊界旋轉(zhuǎn)的問題代碼如下：
void?rotateMatrix(vector<vector<int>>?&matrix)?{
????int?a?=?0,?b?=?0,?c?=?matrix.size()?-?1,?d?=?matrix[0].size()?-?1;
????while?(a?<=?c?&&?b?<=?d)?{
????????rotateEdge(a++,?b++,?c--,?d--,?matrix);?//?旋轉(zhuǎn)指定對角所在正方形的邊界
????}
}
接下來，我們要解決的就是如何將一個矩形邊界旋轉(zhuǎn)的問題了。
我們先考慮四個角：
邊界旋轉(zhuǎn)的四個角再考慮第二個點(diǎn)：
旋轉(zhuǎn)邊界的第二個點(diǎn)聰明的朋友可能已經(jīng)發(fā)現(xiàn)了，這個跟遍歷某一個邊界的一邊非常像，我們原地交換四個點(diǎn)只需要5步，再加上遍歷某一邊，旋轉(zhuǎn)一個邊界就此完成。
代碼如下：
void?rotateEdge(int?a,?int?b,?int?c,?int?d,?vector<vector<int>>?&matrix)?{
????for?(int?i?=?0;?i?//?每一行要剔除最后一個點(diǎn)
????????int?temp?=?matrix[a][b?+?i];?????????????????//?暫存左上角的點(diǎn)
????????matrix[a][b?+?i]?=?matrix[c?-?i][b];?//?把左下角的點(diǎn)放到左上角?
????????matrix[c?-?i][b]?=?matrix[c][d?-?i];?//?把右下角的點(diǎn)放到左下角
????????matrix[c][d?-?i]?=?matrix[a?+?i][d];?//?把右上角的點(diǎn)放到右下角
????????matrix[a?+?i][d]?=?temp;?????????????????????????//?把暫存的左上角的點(diǎn)放到右上角
????}
}
“之”字型打印矩陣
【題目】 給定一個矩陣matrix，按照“之”字形的方式打印這 個矩陣，例如:
“之”字型打印“之”字形打印的結(jié)果為：
1，2，5，9，6，3，4，7，10，11，?8，12
【要求】 額外空間復(fù)雜度為O(1)。
【解法說明】和之前的題目類似，一旦我們陷于考慮局部的坐標(biāo)如何變換，就會陷入細(xì)節(jié)邊界之中，難以快速解決這道題目。我們換個思路，將整個過程切分為：給定兩個對角點(diǎn)坐標(biāo)，遍歷對角線，然后尋找兩個對角點(diǎn)坐標(biāo)的變化規(guī)律。
給定兩個對焦點(diǎn)坐標(biāo)，遍歷該對角線，實(shí)現(xiàn)起來非常簡單：
void?printDiagonal(int?a,?int?b,?int?c,?int?d,?vector<vector<int>>?&matrix)?{
????while?(a?>=?c?&&?b?<=?d)?{?//?從左下到右上的遍歷方式
??????????cout?<"?";
????}
}
遍歷對角線圖中的(a, b)為對角線的左下角頂點(diǎn)，其中a、b均是變量，從左到右分別為每次變換的位置；一開始(a, b)和(c, d)都是點(diǎn)1，即matrix[0][0]；我們觀察兩個點(diǎn)的變換軌跡，可以發(fā)現(xiàn)，(a, b)先向下走，到底部再向右走；而(c, d)先向右走，到達(dá)最右邊才向下走。
與此同時，每完成一次對角線遍歷，我們發(fā)現(xiàn)，遍歷的方向會發(fā)生改變，因此我們使用一個bool類型的isUp來記錄狀態(tài)。
因此，對角線函數(shù)需要進(jìn)行修改：
void?printDiagonal(int?a,?int?b,?int?c,?int?d,?vector<vector<int>>?&matrix,?bool?isUp)?{
????if?(isUp)?{
????????while?(a?>=?c?&&?b?<=?d)?{
????????????cout?<"?";
????????}
????}?else?{
????????while?(a?>=?c?&&?b?<=?d)?{
????????????cout?<"?";
????????}
????}
}
遍歷所有對角線：
void?ZigZagPrint(vector<vector<int>>?&matrix)?{
????bool?isUp?=?true;
????int?a?=?0,?b?=?0,?c?=?0,?d?=?0;
????while?(c?!=?matrix.size())?{?//?c?如果為?n，說明右上角的對角線頂點(diǎn)已經(jīng)到達(dá)矩陣的右下角，所有對角線都被遍歷了
????????printDiagonal(a,?b,?c,?d,?matrix,?isUp);
????????isUp?=?!isUp;
????????b?=?(a?==?matrix.size()?-?1)???b?+?1?:?b;?//?注意，我們要先更新b，然后才更新a
????????a?=?(a?==?matrix.size()?-?1)???a?:?a?+?1;
????????c?=?(d?==?matrix[0].size()?-?1)???c?+?1?:?c;?//同樣的，先更新c，再更新d
????????d?=?(d?==?matrix[0].size()?-?1)???d?:?d?+?1;
????}
}
在行列都排好序的矩陣中找數(shù)
【題目】 給定一個有N*M的整型矩陣Matrix和一個整數(shù)K， Matrix的每一行和每一 列都是排好序的。實(shí)現(xiàn)一個函數(shù)，判斷K 是否在 Matrix中。例如：
從排好序的矩陣中找數(shù)如果K為5，返回true；如果K為10，返回false。
【要求】 時間復(fù)雜度為O(N+M)，額外空間復(fù)雜度為O(1)。
【解法說明】如果我們遍歷完整個矩陣，需要O(N^2)，而題目中要求O(N+M)的復(fù)雜度，因此我們就需要根據(jù)特殊的數(shù)據(jù)布局來考慮更優(yōu)的解法。懂得二分法的朋友肯定知道，我們在一個排好序的數(shù)組中找一個數(shù)，從中間找起是最快的；這里也是類似，不過這里的中間在哪里呢？
事實(shí)上，考慮數(shù)據(jù)的分布，左上角必然是最小值，右下角必然是最大值，而中間線，正好在左下角到右上角的對角線上：
從中間線出發(fā)假設(shè)我們找K=5，從右上角開始，發(fā)現(xiàn)4 < 5，所以向下找，為什么？因?yàn)樾辛卸际前错樞蚺藕玫模?左邊的數(shù)都是比4小的，既然5比4大，那么在左邊就不可能找到5了：
4的左邊已經(jīng)不存在5了接下來我們繼續(xù)比較，發(fā)現(xiàn)8 > 5，所以向左找，因?yàn)橄旅娌豢赡苡?了：
8的下面不可能存在5按照上面的方式，我們完成搜索：
找到5，返回true我們仔細(xì)考慮下過程，即使K在左下角，我們從右上角開始找，那么最終耗費(fèi)的時間也只是O(N+M)，N 為寬度，M 為長度。
代碼實(shí)現(xiàn)：
bool?findKInSortedMatrix(vector<vector<int>>?&matrix,?int?k)?{
????int?a?=?0,?b?=?matrix[0].size()?-?1;
????while?(a?<=?matrix.size()?-?1?&&?b?>=?0)?{
????????if?(matrix[a][b]?==?k)?{?//?found
????????????return?true;
????????}?else?if?(matrix[a][b]?//?如果當(dāng)前點(diǎn)小于?K，向下走
????????????a++;
????????}?else?{?//?如果當(dāng)前點(diǎn)大于?K，向左走
????????????b--;
????????}
????}
????return?false;?//?not?found
}
其他算法推薦：二分法
1、二分法題型小結(jié)
2、兩道看似簡單的面試高頻算法題
3、如何理解二分查找？生活中還能用來設(shè)計騙局？
4、二分搜索只能用來查找元素嗎？
推薦閱讀
全部文章詳細(xì)分類與整理（算法+數(shù)據(jù)結(jié)構(gòu)+計算機(jī)基礎(chǔ)）
【吐血整理】百度云珍藏了四年書籍+臨時搜索，帥地給大家整理了幾百本常用電子書(附下載鏈接)?。?/strong>